简介
Floyd-Warshall算法是求解多源最短路的算法之一，核心思想是动态规划，适用于不包含负环（负权回路）的图。时间复杂度$O(n^{3})$，空间复杂度$O(n^{2})$。
Floyd-Warshall算法
对于任何一个点而言，i到j的最短距离不外乎i到j经过k和不经过k两种可能，所以可以令$k=1,2,3,\ldots,n$，检查$dis(i, j)$与$dis(i, k)+dis(k, j)$的大小，在此$dis(i, k)$与$dis(k, j)$分别是目前为止所知的i到k与k到j的最短距离，因此$dis(i, k)+dis(k, j)$就是i到j经过k的最短距离。
所以，若有$dis(i, j) \gt dis(i, k)+dis(k, j)$，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的距离$dis(i, j)$更新为$dis(i, k)+dis(k, j)$，更新完后$dis(i, j)$就是目前的i到j的最短距离。重复这一过程，最后当遍历完k时，$dis(i, j)$里面存放的就是i到j之间的最短距离了。
我们定义数组$dp[k][x][y]$表示只允许经过结点1到k，结点x到结点y的最短路径长度，那么状态转移方程就是$dp[k][x][y] = min(dp[k-1][x][y], dp[k-1][x][k]+dp[k-1][k][y])$，可以发现第一维是没有用的，于是直接改成$dp[x][y] = min(dp[x][y], dp[x][k]+dp[k][y])$。
代码实现很简单，不过要注意循环的嵌套循序，k作为阶段，枚举时的循环要放在最外层：
1void floyd(int n)
2{
3 for(int k=1; k<=n; k++)
4 for(int i=1; i<=n; i++)
5 for(int j=1; j<=n; j++)
6 g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
7}
*传递闭包
Floyd算法不仅可以求最短路，也可以维护关系求传递闭包。建立邻接矩阵$f[i][j]$表示i和j是否有关系，跑一遍floyd，然后检查$f[i][j]&f[j][i]$是否为1。下面给出bitset优化版本，时间复杂度$O(\frac{n^{3}}{w})$。
1// std::bitset<SIZ> f[SIZ];
2void floyd(int n)
3{
4 for(int k=1; k<=n; k++)
5 for(int i=1; i<=n; i++)
6 if(f[i][k]) f[i] = f[i] | f[k];
7}
模板
1const int inf = 0x3f3f3f3f;
2const int mxn = 1e3 + 5;
3
4int g[mxn][mxn], pre[mxn][mxn];
5
6void graph_init(int n)
7{
8 for(int i=1; i<=n; i++){
9 for(int j=1; j<=n; j++)
10 g[i][j] = inf;
11 g[i][i] = 0;
12 }
13}
14
15void floyd_init(int n)
16{
17 for(int i=1; i<=n; i++){
18 for(int j=1; j<= n; j++){
19 pre[i][j] = (g[i][j]==inf ? -1 : j);
20 }
21 }
22}
23
24void floyd(int n)
25{
26 for(int k=1; k<=n; k++)
27 for(int i=1; i<=n; i++)
28 for(int j=1; j<=n; j++){
29 if(g[i][k]+g[k][j] < g[i][j]){
30 g[i][j] = g[i][k]+g[k][j];
31 pre[i][j] = pre[i][k];
32 }
33 }
34}
35
36int main()
37{
38 int n, m;
39 scanf("%d %d", &n, &m);
40 graph_init(n);
41
42 for(int i=0; i<m; i++)
43 {
44 int u, v, w;
45 scanf("%d %d %d", &u, &v, &w);
46 g[u][v] = w;
47 }
48 floyd_init(n);
49 floyd(n);
50
51 for(int i=1; i<=n; i++){
52 for(int j=1; j<=n; j++)
53 printf("%d ", g[i][j]);
54 printf("\n");
55 }
56
57 for(int i=1; i<=n; i++){
58 for(int j=1; j<=n; j++)
59 printf("%d ", pre[i][j]);
60 printf("\n");
61 }
62
63 return 0;
64}
65
66/*
67Sample Input:
68
694 5
701 2 2
711 3 4
722 4 1
733 2 1
743 4 8
75
76Sample Output:
77
780 2 4 3
791061109567 0 1061109567 1
801061109567 1 0 2
811061109567 1061109567 1061109567 0
821 2 3 2
83-1 2 -1 4
84-1 2 3 2
85-1 -1 -1 4
86
87*/