Floyd-Warshall 算法详解

Mohammed Islam Hadjoudj

资深运筹学工程师

1. Floyd-Warshall 算法简介

Floyd-Warshall 算法解决的是全源最短路径问题。给定一个带权有向图，它会求出每一对顶点之间的最短距离，而不只是从某个选定起点出发的距离。算法结束时，你会得到一张完整的距离矩阵：查任意起点与任意终点，答案都已经在那里。

这与 Dijkstra 算法和 Bellman-Ford 算法回答的问题不同。那两者是单源算法：你给它一个起点，它告诉你其余每个顶点离这个起点有多远。Floyd-Warshall 则一次性回答所有这些问题，覆盖每一个可能的起点，只需运行一遍。

这个算法的了不起之处，在于它做到这一点所需的东西极少。没有优先队列，没有访问集合，也没有递归。整个算法就是对一个矩阵做三重嵌套循环，其正确性建立在一个取自动态规划的清晰想法之上。它还能处理负权边，而 Dijkstra 做不到；并且作为顺带的副产品，它会报告负环的存在。

2. 全源与单源之比：为什么不直接重复跑 Dijkstra？

一个显而易见的反问是：你完全可以从每个顶点各跑一次单源算法。这个思路是正当的，有时甚至更可取，因此值得把各自的适用场景说清楚。

用二叉堆从全部 V 个顶点分别运行 Dijkstra，代价是 O(V * E log V)。在稀疏图中，边数 E 接近 V，这大约是 O(V2 log V)，明显优于 Floyd-Warshall。而在稠密图中，E 接近 V2，同样的重复大约要 O(V3 log V)，此时 Floyd-Warshall 恒定的 O(V3) 反而更优。

另有两点考量，往往在复杂度之前就决定了选择：

• 负权重。只要存在负权边，重复运行 Dijkstra 就是错误的。你必须改用 Bellman-Ford，总代价为 O(V2 * E)，或者先用 Johnson 算法对图重新赋权。Floyd-Warshall 直接接受负权边。
• 简洁性。Floyd-Warshall 大约只有五行代码，不需要任何辅助数据结构。在排程、路由表和竞赛编程中常见的那类小而稠密的图上，这份可靠性比渐近复杂度上的优势更值钱。

3. 核心思想：中间顶点

Floyd-Warshall 的巧思在于给问题加上一个限制，使它易于逐步放宽。它不一上来就问"从 i 到 j 的最短路径是什么？"，而是问一个更窄的问题：

如果只允许把某个许可集合中的顶点用作中转站，那么从 i 到 j 的最短路径是什么？

把顶点编号为 1 到 V。将许可集合定义为前 k 个顶点，并记 dk(i, j) 为只使用 {1, 2, ..., k} 作中间顶点时，从 i 到 j 的最短距离。端点 i 和 j 始终允许，无论它们是否落在许可集合内；受限制的只是严格位于两者之间的顶点。

这个定义的两个极端很能说明问题。当 k = 0 时没有任何顶点可作中转，因此 d0(i, j) 就是从 i 到 j 的直接边权，若不存在这样的边则为无穷大。当 k = V 时所有顶点都被允许，因此 dV(i, j) 就是真正不受限制的最短距离。算法正是把前者推进到后者的那套机制。

4. 递推关系

假设你已经知道 dk-1 的全部取值，现在想求 dk。考虑允许使用 {1, ..., k} 的、从 i 到 j 的最短路径。恰好只有两种可能，且二者互斥：

1. 该路径不经过顶点 k。那么它只用到 {1, ..., k-1}，长度即为 dk-1(i, j)，这个值你已经有了。
2. 该路径经过顶点 k。由于最短路径不会重复经过同一顶点，它恰好穿过 k 一次。这把它拆成从 i 到 k 与从 k 到 j 两段，且两段都不能再把 k 当作中转站。因此长度为 dk-1(i, k) + dk-1(k, j)，这两项同样都已知。

最短路径取两者中较小的一个，于是得到算法核心的递推式：

d[k][i][j] = min( d[k-1][i][j],
                  d[k-1][i][k] + d[k-1][k][j] )

用一句话说：只有当绕道 k 再前往 j 比不经过它时找到的最佳路线更短，走 k 才划算。这是最纯粹形态的动态规划：每个子问题只求解一次，存下来反复取用。

实践中没有人会保存 V 张独立矩阵。所有取值可以在同一张 V x V 矩阵上原地更新，因为在第 k 轮迭代期间，d(i, k) 与 d(k, j) 这两类元素不可能改变：更新它们需要用到 d(k, k)，而只要图中没有负环，该值恒为 0。因此读到本轮已被覆写的值也无妨，空间开销随之从 O(V3) 降到 O(V2)。

5. 逐步执行演示

抽象的递推式一旦代入数字就会变得清晰。取一个含四个顶点的有向图，边如下：

• 1 -> 2，权重 5
• 1 -> 4，权重 10
• 2 -> 3，权重 3
• 3 -> 4，权重 1

仅根据这些边初始化矩阵。对角线为 0，因为每个顶点到自身无需代价；所有缺失的边记为无穷大。

k = 0（仅直接边）

        1     2     3     4
  1     0     5     inf   10
  2     inf   0     3     inf
  3     inf   inf   0     1
  4     inf   inf   inf   0

第 k = 1 轮。现在允许把顶点 1 用作中转。任何更新都需要一个有限的 d(i, 1)，但第 1 列除对角线外全是无穷大，因为没有任何边指向顶点 1。没有变化。

第 k = 2 轮。顶点 2 可用了。第 2 行给出有限的 d(2, 3) = 3，第 2 列给出有限的 d(1, 2) = 5，由此产生一处可能的改进：

• d(1, 3) 原为无穷大。经顶点 2 变为 5 + 3 = 8，更新为 8。

第 k = 3 轮。顶点 3 可用，且 d(3, 4) = 1。有两处改进：

• d(1, 4) 原本走直接边为 10。经顶点 3 变为 d(1, 3) + d(3, 4) = 8 + 1 = 9，更新为 9。
• d(2, 4) 原为无穷大。经顶点 3 变为 3 + 1 = 4，更新为 4。

请注意，d(1, 4) 的改进依赖于 d(1, 3) = 8，而这是上一轮才发现的值。算法正是用已经证明过的短路径，拼出更长的路径。

第 k = 4 轮。顶点 4 没有出边，第 4 行除对角线外全为无穷大，任何路径都不可能有意义地经过它。没有变化，算法结束。

最终结果（全部点对）

        1     2     3     4
  1     0     5     8     9
  2     inf   0     3     4
  3     inf   inf   0     1
  4     inf   inf   inf   0

1 -> 4 的答案是 9，走 1 -> 2 -> 3 -> 4，代价为 5 + 3 + 1，优于权重为 10 的直接边。矩阵中剩下的无穷大是正确结果，而非尚未算完：没有边进入顶点 1，所以任何顶点都到不了它。

6. 实现与伪代码

这个算法短到可以背下来。其中比其他任何细节都更重要的一点，是循环的顺序。

function FloydWarshall(W, V):
    // W[i][j] = 边 i -> j 的权重，不存在则为 Infinity
    // dist 是一个 V x V 矩阵

    for i from 1 to V:
        for j from 1 to V:
            dist[i][j] = W[i][j]
        dist[i][i] = 0

    // k 必须是最外层循环
    for k from 1 to V:
        for i from 1 to V:
            for j from 1 to V:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

k 必须是最外层循环。这是把该算法写错的最常见方式。递推式要求：在进入 k + 1 之前，每一对 (i, j) 都必须相对于中间顶点 k 更新完毕。若把 k 放在内层，矩阵就会以一种没有意义的顺序被填充，得到的距离看似合理，实则并非最优。

一个实现上的注意点：如果你用 INT_MAX 这类很大的哨兵值而非真正的浮点无穷大来表示无穷，dist[i][k] + dist[k][j] 可能溢出并回绕成负数，而比较会欣然接受它。要么使用真正的无穷大，要么给加法加上保护：只要任一操作数是哨兵值就跳过本次更新。

7. 时间与空间复杂度

• 时间：O(V3)。三重嵌套循环各运行 V 次，循环体只有一次比较和一次赋值。这里没有值得区分的最好或最坏情况：无论图实际上有多少条边，算法对任何输入都恰好执行 V3 次松弛判断。
• 空间：O(V2)。一张原地更新的距离矩阵。若还想重建路径，则需要再来一张同样大小的矩阵。

对 E 不敏感正是它的标志性特征。四个顶点三条边的图，与四个顶点十二条边的图，代价完全相同。这在稀疏图上是浪费，在稠密图上则恰到好处。作为交换，它的常数因子很小，内存访问模式规整且对缓存友好，因此在几百个顶点规模的图上，Floyd-Warshall 的实际表现常常好于其渐近复杂度所暗示的。

8. 负权边与负环检测

Floyd-Warshall 无需任何修改即可接受负权边。它的递推式从不假设延长一条路径就会增加其长度，而正是这一假设让 Dijkstra 算法在负权输入上失效。

负环则是另一回事，任何算法在负环存在时都无法给出有意义的最短距离：你可以无限次绕行该环，把代价压到没有下界。但 Floyd-Warshall 让你能免费察觉这一点。算法结束后检查对角线即可：

for i from 1 to V:
    if dist[i][i] < 0:
        报告 "检测到负环"

对角线初始化为 0。一个顶点到自身的距离之所以可能变成负数，只可能是存在一条以它为起点和终点、总权重小于零的闭合走道，而这正是负环的定义。Bellman-Ford 需要专门再遍历一次所有边才能得出同样的结论，Floyd-Warshall 只需扫一眼它早已算好的 V 个元素。

请留意这项检查的范围：它标示出相应顶点所参与的任何负环。若对角线干净，矩阵中的每个距离都可信；若不干净，矩阵其余位置上的有限值应视为无意义，而不只是不够精确。

9. 重建真实路径

距离矩阵记录了两个顶点相距多远，却没有记录是哪条路线达成的。要还原路线需要额外一张矩阵，而最省事的方案是为每一对顶点保存路径上的下一个顶点。

只要存在直接边就把 next[i][j] 初始化为 j，否则置空。此后每当主循环经由 k 改进了 dist[i][j]，就继承新路线的第一步：

if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] = dist[i][k] + dist[k][j]
    next[i][j] = next[i][k]

赋的值是 next[i][k]，而不是 k。从 i 到 j 这条改进后行程的第一步，就是从 i 到 k 那段行程的第一步，而那很可能是另一个完全不同的顶点。读出路径于是变成一次短短的行走：从 i 出发，反复沿 next 前进，抵达 j 时停止。这只额外花费 O(V2) 的空间，几乎不增加时间。

10. 变体与实际应用

这套三重循环结构的适用范围远不止最短路径，因为递推式只需要两种运算：一种把两段拼起来，一种在若干候选中做选择。

传递闭包（Warshall 算法）

把加法换成逻辑与、把取最小换成逻辑或，同样的循环便可计算可达性：不计代价，只问每一对顶点之间是否存在路径。这正是 Warshall 1962 年的原始成果，也是这个合并后的算法同时冠以两人之名的原因。它出现在编译器的数据流分析、依赖关系求解和数据库查询规划之中。

最宽路径与瓶颈问题

把加法换成取最小、把取最小换成取最大，算法便会找出最窄环节尽可能宽的那条路线。这是网络中最大带宽路由与物流中运力规划的天然表述方式。

网络路由与时延矩阵

网络运营方常常需要一张覆盖拓扑中所有节点对的完整时延或跳数矩阵。骨干网拓扑往往稠密而顶点数不多，这正是 Floyd-Warshall 的主场。

货币套利

把货币建模为顶点、把汇率建模为边。对每个汇率取负对数，汇率的乘法就变成了权重的加法，而一个有利可图的套利回路就变成了一个负环。此时对角线检查会告诉你是否存在套利机会，next 矩阵则可还原出具体的交易顺序。

11. 学术资源与历史

这个算法的归属异常纠缠。数位研究者在相隔不过数年的时间里，各自独立地得出了同样的三重循环。

• Stephen Kleene（1956）在把有限自动机转换为正则表达式时描述了其底层过程，从结构上看那正是同一种闭包计算。
• Bernard Roy（1959）在 Transitivite et connexite 中以基本现代的形式发表了该算法，比赋予它通用名称的那些论文早了三年。
• Stephen Warshall（1962）发表了传递闭包版本，证明了以他命名的布尔矩阵定理。
• Robert W. Floyd（1962）在 Communications of the ACM 上以一篇极其简短的札记 Algorithm 97: Shortest Path 发表了最短路径版本。
• Peter Ingerman（1962）同年在同一刊物上描述了如今标准的三重嵌套循环写法。

若需要附有完整正确性证明的严谨论述，标准参考书是 Cormen、Leiserson、Rivest 与 Stein 合著的 Introduction to Algorithms 中关于全源最短路径的一章。想为稀疏图比较各种方案的读者，还应研究 Johnson 算法，它通过对图重新赋权，使得即便存在负权边，重复运行 Dijkstra 依然有效。完整文献信息列于本文末尾。