Floyd-Warshall计算器

伪代码

三层嵌套循环和一行更新语句。全部精妙之处都在循环顺序上：k 必须是最外层循环，弄错这一点正是经典错误。

FloydWarshall(图):
    dist = V 乘 V 的矩阵，全部置为无穷大
    对每个结点 v:      dist[v][v] = 0
    对每条边 (u,v,w):  dist[u][v] = w

    对 k 遍历所有结点:            // 中转点
        对 i 遍历所有结点:        // 起点
            对 j 遍历所有结点:    // 终点
                若 dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next[i][j] = next[i][k]   // 用于还原路径

    // 存在负环当且仅当某个 v 满足 dist[v][v] < 0

不变式是：在 k 这一轮结束之后，dist[i][j] 表示只允许使用前 k 个结点作为中转时，从 i 到 j 的最短路径。要让这一点成立，k 就必须在最外层：正是它每次把允许的中转结点集合扩大一个。把 k 放到内层同样会终止，而且给出看起来合理的数字，这恰恰是该错误极难被发现的原因。

分步示例演算

在一个小型有向图上运行 Floyd-Warshall，观察某个表项如何随着允许中转结点集合的扩大而两次改进。

示例图: 有向边 A 到 B (3)、A 到 C (8)、B 到 C (2)、B 到 D (7) 和 C 到 D (1)。

1. 初始化. 只填入直接边。从 A 出发：到 B 为 3，到 C 为 8，到 D 不可达。从 B 出发：到 C 为 2，到 D 为 7。从 C 出发：到 D 为 1。对角线全部为 0。
2. k = A. 没有任何变化。没有边指向 A，因此对其他任何 i，dist[i][A] 都是无穷大，也就没有路径能经由 A 中转。
3. k = B. 出现两处改进。dist[A][C] 由 8 降为 dist[A][B] + dist[B][C] = 3 + 2 = 5。dist[A][D] 由无穷大降为 3 + 7 = 10，这是 A 到 D 的第一条有限路径。
4. k = C. 又有两处改进。dist[A][D] 再次改进，由 10 降为 dist[A][C] + dist[C][D] = 5 + 1 = 6；注意它用到的正是 k = B 那一轮刚刚改进过的 dist[A][C]。dist[B][D] 由 7 降为 2 + 1 = 3。
5. k = D. 没有任何变化，因为 D 没有出边，无法充当中转点。

从 A 出发的最终距离是到 B 为 3、到 C 为 5、到 D 为 6。A 到 D 这一项改进了两次，从无穷大到 10 再到 6，这直接展示了它的分层特性：k = C 那一轮之所以能找到更好的路线，正是因为 k = B 那一轮已经先改进了 A 到 C。这种依赖关系就是 k 必须放在最外层循环的原因。

复杂度及其来源

时间: O(V^3) · 空间: O(V^2)

三层嵌套循环遍历所有结点，恰好产生 V 的立方次迭代，每次做常数级的工作。既没有提前退出，也不依赖边的数量，因此这个算法在稀疏图上和在稠密图上的代价完全相同。空间是 V 乘 V 的距离矩阵；若还想还原路径而不只是路径长度，则再加一个矩阵。实践中 V 的立方在几千个结点以内还可以接受；到了 5000 个结点就是一千二百五十亿次操作，此时在稀疏图上从每个结点跑一次 Dijkstra，即 O(V·E·log V)，反而成为更好的选择。

何时使用弗洛伊德-沃歇尔算法，何时不宜

Floyd-Warshall 胜在稠密与简洁，在大规模稀疏图上则明显落败。

常见陷阱

• 把 k 循环放在最外层以外的任何位置. 这是 Floyd-Warshall 的标志性错误。k 一旦放在内层，不变式就不成立，某些点对的结果会悄无声息地偏大。它既不报错，看上去也很合理，因此能轻易躲过粗略的测试。顺序必须是 k、然后 i、然后 j。
• 在无穷大上做加法. 若把无穷大表示为一个很大的整数，dist[i][k] + dist[k][j] 会溢出并回绕成负数，从而造出根本不存在的最短路径。请给这次加法加上保护，或者使用一个小到即便翻倍也不会溢出的哨兵值。
• 在含负环的图上运行却不做检查. 算法不会失败，它只会返回没有意义的数值。循环结束后，任何满足 dist[v][v] 小于零的结点都位于某个负环上。在信任这个矩阵之前请先做这项检查。
• 把它用在大规模稀疏图上. V 的立方完全忽略了 E。在一个有 10000 个结点、30000 条边的图上，Floyd-Warshall 要做一万亿次操作，而从每个结点跑 Dijkstra 只需几亿次。
• 忘记初始化对角线. dist[v][v] 必须从 0 开始而不是无穷大。让它保持无穷大会破坏最初的那几次松弛，并悄悄污染其后的一切。

常见问题

Floyd-Warshall 算法有什么用？

它在一次运行中计算带权图中所有结点对之间的最短路径。它用于路径规划中的全点对距离表、计算关系的传递闭包、求图的直径、同时检测所有货币对之间的套利机会，以及任何你将要查询大量不同起点终点对的场景。

Floyd-Warshall 的时间复杂度是多少？

O(V 的立方) 时间和 O(V 的平方) 空间，完全不依赖边的数量。三层嵌套循环遍历所有结点，内部只做常数级工作，而且没有提前终止。这使它对稠密程度不敏感，在稠密图上是优点，在稀疏图上则是严重缺点。

为什么 k 必须是最外层循环？

因为 k 代表允许充当中转点的结点集合，而算法是一次扩大一个结点地增长这个集合的。在某个 k 这一轮结束之后，每个表项在「只使用前 k 个结点作为中转」的意义下都是正确的。若 k 不在最外层，这条不变式永远不成立，算法会给出偏大的距离而且不报任何错。

Floyd-Warshall 能处理负权重吗？

能，只要不存在负环，负权边就没有问题。算法结束后，对角线上出现负值，也就是 dist[v][v] 小于零，说明 v 位于某个负环上，与它相关的距离也就没有意义了。

什么时候应该用 Dijkstra 而不是 Floyd-Warshall？

当图是稀疏的且权重非负时。从每个结点跑 Dijkstra 的代价是 O(V·E·log V)，在边数远少于 V 的平方的图上，这比 V 的立方快得多。Floyd-Warshall 则胜在稠密图、小规模图，以及你想要最简短实现的时候。