通过dij，ford，spfa等算法可以快速的得到单源点的最短路径，如果想要得到图中任意两点之间的最短路径，当然可以选择做n遍的dij或是ford，但还有一个思维量较小的选择，就是floyd算法。
多源最短路径算法
Floyd算法
思维
先直观做个思考，一张图，任意两个点，已知两点间的路径权值，如果在图中能够找到一个点插入到这两点的路径之中，使得构成的路径权值小于之前的路径权值。就可以认为这条路比之前的路更短，这个点是属于两点间最短路径的。由此可以得到一个递推公式：
[e[u][v]=min(e[u][v],e[u][k]+e[k][v])
]
问题就转换成了e[u][k],e[k][v]最短路径的问题，这就是一种动态规划。
只要把图枚举一遍就可以得到所有点之间的最短路径：
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
说到动态规范，总会感叹递推式的优美，但是有没有想过，为什么k循环在最外层，而且由于e[i][k]，e[k][j]也是在不断更新，而不是恒定的最小值，所以如何保证算法在最后一次松弛更新的时候，e[i][k]，e[k][j]一定是最小的。
我们用归纳法（一生之敌）做一次证明：
- 不妨做个命题：假设任意两点i和j之间的路径上可选择经过的结点集合中，座号最大的是x，当k=x的时候，d[i][j]得到最小值。
- 当i，j两点之间路径可选择经过结点仅有一个点时候，命题是成立的。
- 设i-x中座号最大的为x1,x-j中座号最大的为x2。
- 显然x>x1,x>x2。
- 假设此时命题成立，则k=x1时，d[i][x]最小，k=x2时，d[x][j]最小。
- 由此可以得到k=x的时候d[i][x]+d[x][j]已经是最小了,那么e[i][j]=min(e[i][j]，e[i][x]+e[x][j])必然可以得到最小值。
由此可以证明在k循环完后就能够得到最小的。当然也可以画张图直观的感受一下。
代码实现
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1000;
int e[MAX][MAX];
int n, m;
void Floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
}
int main() {
cin >> n >> m;
const int inf = 100000;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) e[i][j] = 0;
else e[i][j] = inf;
int u, v, w;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
e[u][v] = w;
e[v][u] = w;
}
Floyd();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cout << e[i][j] << " ";
return 0;
}