all-pairs · 全源最短路

全源最短路：Floyd 与 Johnson

最短路径：拆解 Dijkstra 解决的是单源问题：给定一个起点，求它到其余各点的距离。真实场景里问的常是另一种：任意两点之间的距离表，路由表要它、社交网络的直径要它、把一组不等式解出来也要它（见差分约束）。本页讲全源最短路的两条主线：Floyd-Warshall 的矩阵递推与 Johnson 的重赋权，并顺带看同一副三重循环骨架还能算出什么。

1 · 从单源到全源

最直接的做法是把单源算法跑 $V$ 遍。边权非负时每遍是 Dijkstra，总代价 $O(V(E + V\log V))$ ；出现负权边就得换 Bellman-Ford，总代价 $O(V^2E)$ 。这条路走得通，但它把全源问题当成了 $V$ 个互不相干的问题， $V$ 遍之间没有任何信息复用。

Floyd-Warshall 换了一个记账单位：不维护 $V$ 张 dist 数组，只维护一张 $V \times V$ 的矩阵 $d[i][j]$ 。初始时 $d[i][i] = 0$ 、有边的 $d[i][j]$ 取边权、其余为无穷。整个算法只对这张矩阵反复改写，三层循环跑完即得答案。

2 · 中转点集的前缀

矩阵递推的归纳维不是「路径长度」也不是「已确定的点集」，而是一个更朴素的东西：允许哪些点出现在路径中间。

定义 2.1（受限最短距离） 把点按固定次序编号。 $d_k[i][j]$ 表示从 $i$ 到 $j$ 、且中间经过的点全部取自前 $k$ 个点的最短距离； $d_0[i][j]$ 即不许中转，只能走直连边。

在这个定义下，从 $k-1$ 到 $k$ 只多了一个可用的中转点，一条只用前 $k$ 个点中转的路径，要么根本没用到第 $k$ 个点，要么恰好用它一次——用它两次意味着中间夹了一个回路，去掉回路不会变长（此处假定无 negative cycle）。两种情形各自的最优值就是递推的两项：

d_k[i][j] = \min\bigl(d_{k-1}[i][j],\; d_{k-1}[i][k] + d_{k-1}[k][j]\bigr)

实现里那张矩阵只有一份， $k$ 这一维被滚动掉了，而滚动是安全的： $d_k[i][k] = d_{k-1}[i][k]$ ， $d_k[k][j] = d_{k-1}[k][j]$ 。第 $k$ 个点作为路径端点出现时，允不允许它当中转点并不影响结果。这两个等式让递推用到的那两格在本轮改写前后完全一致，原地更新与分层更新给出同一张矩阵。

$k$ 因此是 DP 的阶段维，必须待在最外层：整张矩阵一起从「允许前 $k-1$ 个」推进到「允许前 $k$ 个」。

警示 · 把 $k$ 挪到最内层，写出来的是「对每一对 $(i, j)$ 各自枚举一次中转点」，那不是上面的递推，也算不对。本页测试里保留了这个错误版本对照：在正权图上，它给出 $d[B][A] = 10$ ，而正确值是 7。原因是 $B \to C \to D \to A$ 这条路要求 $d[C][A]$ 先算好，可 $(C, A)$ 排在 $(B, A)$ 之后才轮到，此刻还是无穷，只剩 $B \to D \to A$ 的 $6 + 4$ 可用。三层循环的顺序不是风格问题。

图 2-1 · Floyd-Warshall 的逐格执行。可切换图与粒度：每格一帧时能看清「绕道

k

」用的是哪两格，每轮

k

一帧时能看清矩阵按阶段整体推进。

3 · 传递闭包

把递推里的 $\min$ 换成或、把加法换成与，同一副骨架算的就是可达性： $r[i][j]$ 表示 $i$ 能否到达 $j$ ，递推变成 $r[i][j] \leftarrow r[i][j] \lor (r[i][k] \land r[k][j])$ 。这就是 Warshall 1962 年给出的 transitive closure 算法 [2]，与 Floyd 同年发表的最短路算法 [1] 是同一个模式在两个半环上的实例： $(\min, +)$ 与 $(\lor, \land)$ 都满足结合律与分配律，递推的正确性只依赖这一点。

代价同样是 $O(V^3)$ ，但每格只占一个 bit，实现里常按机器字打包，一次或运算处理 64 列。

图 3-1 · Warshall 传递闭包的逐格执行。可切换图与粒度，观察 0 如何在某一轮

k

被置 1；矩阵里的 1 表示行点到得了列点。

4 · 负环与对角线

$d[i][i]$ 起初是 0。若某一轮之后它变成了负数，说明存在一条从 $i$ 回到 $i$ 且总权为负的回路，即 negative cycle。检测不需要额外一趟扫描，看完对角线就有答案。

需要留心的是这张表的其余部分。Floyd 在有 negative cycle 时不会报错，它照常输出一组有限值，而那些值没有意义——本页的 negative cycle 示例图里， $A$ 、 $B$ 、 $C$ 落在一个总权 $-2$ 的环上，算完的 $d[A][B]$ 是 $-1$ ，真实答案却是负无穷，因为绕环任意多圈都合法。同一张表里 $d[D][D]$ 仍是 0， $D$ 不在环上，它只是碰巧没被污染。对角线是唯一可靠的信号，读表之前先看它。

5 · Johnson 的重赋权

Floyd 的 $O(V^3)$ 与图的疏密无关： $V = 2000$ 的稀疏图上，它照样要做八十亿格次计算，而 $V$ 遍 Dijkstra 只要 $O(V(E + V\log V))$ 。跑 Dijkstra 的障碍只有一个——负权边。Johnson 1977 年的办法 [3] 是先把负权边消掉，且消得不改变任何一对点之间谁最短。

做法是给每个点配一个 potential $h[v]$ ，把边权改写成 $w'(u, v) = w(u, v) + h[u] - h[v]$ 。 $h$ 的取法是：接一个超级源点 $q$ ，向每个点连一条 0 权边，跑一次 Bellman-Ford， $h[v]$ 取 $q$ 到 $v$ 的最短距离。

定理 5.1（重赋权保序且非负） 若图中无 negative cycle，则如上定义的 $h$ 使每条边的 $w' \ge 0$ ；且对任意 $u \to v$ 的路径，其 $w'$ 总权与原总权只差 $h[u] - h[v]$ ，与路径本身无关。

证明非负性即三角不等式： $h$ 是最短距离，故 $h[v] \le h[u] + w(u, v)$ ，移项即 $w'(u,v) \ge 0$ 。至于总权，一条路径 $u = v_0 \to v_1 \to \dots \to v_m = v$ 的 $w'$ 之和是 $\sum w(v_{t-1}, v_t) + \sum (h[v_{t-1}] - h[v_t])$ ，第二项逐项相消只剩 $h[u] - h[v]$ 。这个差值只由两端决定，所以同一对点之间的各条路径被整体平移了同一个量，排序不变。∎

于是算法成形：一次 Bellman-Ford 求 $h$ （顺带完成 negative cycle 检测），一遍改写边权， $V$ 次 Dijkstra，最后按 $d[u][v] = d'[u][v] - h[u] + h[v]$ 撤销偏移。总代价 $O(VE + V^2\log V)$ （Dijkstra 以 Fibonacci heap 实现时单次为 $O(E + V\log V)$ [4]），稀疏图上明显优于 $O(V^3)$ 。

图 5-1 · Johnson 的五个阶段。可切换图，逐阶段看超级源点、potential、重赋权后的边权表，以及距离矩阵如何一行一行填满；negative cycle 的图会在 Bellman-Ford 阶段停下。

实现过程中有两处值得记下。其一，正权图上 $h$ 全为 0，重赋权是一次恒等变换，那趟 Bellman-Ford 白跑：Johnson 在没有负权边时退化成朴素的「逐个源跑 Dijkstra」，多出来的只有一次 $O(VE)$ 的检测。其二，含负权边的示例图上，六条边里有两条的 $w'$ 恰好为 0，它们正是 $h$ 所依据的那棵最短路树上的树边： $h[v] = h[u] + w(u,v)$ 取到等号，改写后自然归零。 $w' = 0$ 的边构成的子图，就是超级源点出发的全部最短路。

建议 · 选哪个不看图大小，看密度与需求。 $V$ 很小（几百以内）或图接近稠密时 Floyd-Warshall 最省事，代码五行、常数极小，还顺手给出 negative cycle 判定与 transitive closure；稀疏图上 Johnson 的渐近优势才兑现得出来。只需要可达性而不需要距离时，Warshall 的位并行版本比两者都快一个数量级。

6 · 参考文献

Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345.
Warshall, S. (1962). A theorem on Boolean matrices. Journal of the ACM, 9(1), 11–12.
Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1), 1–13.
Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615.