第 25 章 全源最短路径 (All-Pairs Shortest Paths)
核心结论
-
问题形式化：给定 n 顶点的带权有向图 \(G=(V,E)\) 与权矩阵 \(W=(w_{ij})\)，求每对顶点 \((i,j)\) 的最短路径权重矩阵 \(D=(d_{ij})\)，其中 \(d_{ij}=\delta(i,j)\)。
-
直接调用单源算法：每个顶点跑一次单源算法——非负权时 Dijkstra 得 \(O(V^2 \lg V + VE)\)（斐波那契堆）；含负权时 Bellman-Ford 得 \(O(V^2 E)\)，对稠密图达 \(O(V^4)\)。
-
最短路径与矩阵乘法（§25.1）：DP 递推 \(l^{(m)}_{ij} = \min_k(l^{(m-1)}_{ik} + w_{kj})\)，与矩阵乘法仅算子不同；用「重复平方」达到 \(\Theta(V^3 \lg V)\)。
-
Floyd-Warshall 算法（§25.2）：以「中间顶点集合」\(\{1,\ldots,k\}\) 为阶段做 DP，递推 \(d^{(k)}_{ij} = \min(d^{(k-1)}_{ij}, d^{(k-1)}_{ik} + d^{(k-1)}_{kj})\)，时间 \(\Theta(V^3)\)，代码紧凑常数小。
-
Johnson 算法（§25.3）：用 Bellman-Ford 求势函数 \(h(v)=\delta(s,v)\)（虚拟源 \(s\)），重赋权 \(\hat{w}(u,v)=w(u,v)+h(u)-h(v)\) 使所有边权非负，然后跑 V 次 Dijkstra，总时间 \(O(V^2 \lg V + VE)\)——稀疏图最快。
-
传递闭包：用 Floyd-Warshall 把每条边权赋 1 即可；或用「逻辑 OR/AND」替代「min/+」得到仅布尔运算的版本，时间同为 \(\Theta(V^3)\)。
|
本章主旨
本章是单源最短路径（第 24 章）的全源推广，覆盖三种核心算法：基于矩阵乘法的慢速 DP（§25.1）、紧凑的 Floyd-Warshall（§25.2）、稀疏图最优的 Johnson（§25.3）。三种算法的差异在于「阶段变量」的选择：§25.1 用「边数」，§25.2 用「中间顶点集合的最大编号」，§25.3 用「势函数重赋权」。除 §25.3 外本章都用邻接矩阵表示；§25.3 是邻接表。Floyd-Warshall 因常数小而成为稠密图首选；Johnson 是稀疏图首选。 |
一、核心概念
本章围绕 6 个核心概念展开：从问题与输入约定出发，先讨论与矩阵乘法的同构 (§25.1)，再给出 Floyd-Warshall (§25.2)，最后介绍 Johnson 的重赋权技巧 (§25.3)。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
全源最短路径 (APSP) |
求每对顶点 \((i,j)\) 的最短路径权重 \(\delta(i,j)\)，输出 \(n \times n\) 矩阵 \(D\)；假设无负权环（否则某些 \(d_{ij} = -\infty\)）。 |
§25.0；输入为权矩阵 \(W\)，w_{ii}=0；可同时求前驱矩阵 \(\Pi\)。 |
最短路径与矩阵乘法 |
DP 递推 \(l^{(m)}_{ij} = \min_k(l^{(m-1)}_{ik} + w_{kj})\)；结构与标准矩阵乘法完全同构——只需把 (\cdot, +, 0) 替换为 (\min, +, \infty)。 |
§25.1；EXTEND-SHORTEST-PATHS 即此运算；重复平方得 \(\Theta(V^3 \lg V)\)。 |
重复平方技术 |
不必逐轮扩展，可「倍增」：计算 \(W, W^2, W^4, \ldots, W^{2^{\lceil \lg(V-1)\rceil}}\)；由封闭性得 \(W^{2^k} = W^{2^k-1} \circ W^{2^k-1}\)。 |
§25.1；只需 \(\lceil \lg(V-1)\rceil\) 次扩展，时间从 \(O(V^4)\) 降到 \(\Theta(V^3 \lg V)\)。 |
Floyd-Warshall 算法 |
以「中间顶点集合」为 DP 维度：\(d^{(k)}_{ij} = \min(d^{(k-1)}_{ij}, d^{(k-1)}_{ik} + d^{(k-1)}_{kj})\)；时间 \(\Theta(V^3)\)，空间可优化至 \(\Theta(V^2)\)。 |
§25.2；可同时构造前驱矩阵 \(\Pi^{(k)}\)；可检测负环（\(d^{(n)}_{ii} < 0\)）。 |
重赋权 (Reweighting) |
引入势函数 \(h:V \to \mathbb{R}\)，令 \(\hat{w}(u,v) = w(u,v) + h(u) - h(v)\)；保持最短路径不变（引理 25.1），且若 \(h(v)=\delta(s,v)\) 则 \(\hat{w} \geq 0\)。 |
§25.3；是 Johnson 算法的关键。 |
Johnson 算法 |
加虚拟源 \(s'\)，Bellman-Ford 求 \(h(v)=\delta(s',v)\)；重赋权后对每顶点跑 Dijkstra；总时间 \(O(V^2 \lg V + VE)\)；含负环时 Bellman-Ford 返回 FALSE。 |
§25.3；稀疏图最快；稠密图 Floyd-Warshall 更优（常数小）。 |
二、详细笔记
25.1 问题形式化与输入约定
What：给定 \(n=|V|\) 顶点的带权有向图 \(G=(V,E)\) 与权矩阵 \(W=(w_{ij})\)，求每对 \((i,j)\) 的最短路径权重，输出矩阵 \(D=(d_{ij})\) 与前驱矩阵 \(\Pi=(\pi_{ij})\)。
Why：全源最短路径是图论核心问题——交通咨询、网络路由、社交网络中心性度量等；矩阵化输出便于后续查询。
How：
权矩阵定义（式 25.1）：
-
最短路径权重 \(\delta(i,j)\)：与第 24 章定义一致；负环可达时 \(\delta = -\infty\)。
-
前驱矩阵：\(\pi_{ij} = \text{NIL}\) 或前驱顶点；行 \(i\) 描述源为 \(i\) 的最短路径树。
-
路径打印：PRINT-ALL-PAIRS-SHORTEST-PATH 递归沿 \(\Pi\) 行回溯。
简单直接算法（baseline）：
-
每个顶点跑一次单源：非负权用 Dijkstra（含负权用 Bellman-Ford）。
-
总时间：\(O(V^2 \lg V + VE)\)（Dijkstra + 斐波那契堆）或 \(O(V^2 E)\)（Bellman-Ford，稠密图 \(O(V^4)\)）。
When：全源最短路径是后续 Floyd / Johnson 算法的目标；当只需少量查询时，直接调用 Dijkstra 反而更经济。
Example：5 顶点 10 边的网络图；输出 5×5 矩阵，每格是 \(\delta(i,j)\)；行 i 给出顶点 i 出发的最短路径树。
25.2 最短路径与矩阵乘法
What：定义 \(l^{(m)}_{ij}\) 为「i 到 j 至多 m 条边的最短路径权重」，递推 \(l^{(m)}_{ij} = \min_k(l^{(m-1)}_{ik} + w_{kj})\)，时间 \(\Theta(n^4)\)（慢速版）。
Why：建立「最短路径 ↔ 矩阵乘法」的同构——这是第一个动态规划解，可直接套用重复平方技巧优化。
How：
递推（式 25.2）：
-
终值（式 25.3）：\(\delta(i,j) = l^{(n-1)}_{ij}\)（无负环时最短路径为简单路径）。
-
EXTEND-SHORTEST-PATHS(L, W)：一次扩展，时间 \(\Theta(n^3)\)，是矩阵乘法的「算子替换」版：min ↔ +, + ↔ ×, +∞ ↔ 0。
-
重复平方：计算 \(W^{2^1}, W^{2^2}, \ldots, W^{2^{\lceil \lg(n-1)\rceil}}\)；最后取不超过 \(W^{n-1}\) 的最大幂。
-
总时间：\(\Theta(n^3 \lg n)\)。
When：展示「DP 与矩阵乘法的同构」是教学价值；实践中 Floyd-Warshall 因常数小更常用。
Example：CLRS 图 25.1 的 5 顶点图，逐轮扩展得到 \(L^{(1)}=W, L^{(2)}, L^{(3)}, L^{(4)}\)，最终 \(L^{(4)}\) 即最短路径权重。
25.3 Floyd-Warshall 算法
What：以「中间顶点集合」为阶段变量的 DP——定义 \(d^{(k)}_{ij}\) 为「所有中间顶点都在 \(\{1,\ldots,k\}\) 内的 i 到 j 最短路径权重」；递推 \(d^{(k)}_{ij} = \min(d^{(k-1)}_{ij}, d^{(k-1)}_{ik} + d^{(k-1)}_{kj})\)；时间 \(\Theta(V^3)\)。
Why：比 §25.1 简单（无需重复平方），常数极小，实践中是稠密图首选；同时可计算前驱矩阵和检测负环。
How：
FLOYD-WARSHALL(W)：
-
\(D^{(0)} = W\)
-
for \(k = 1\) to \(n\):
-
let \(D^{(k)} = (d^{(k)}_{ij})\) be new \(n \times n\) matrix
-
for \(i = 1\) to \(n\):
-
for \(j = 1\) to \(n\):
-
\(d^{(k)}_{ij} = \min(d^{(k-1)}_{ij}, d^{(k-1)}_{ik} + d^{(k-1)}_{kj})\)
-
-
-
-
return \(D^{(n)}\)
性质：
-
正确性：若 k 不在最短路径上则 \(d^{(k)}_{ij} = d^{(k-1)}_{ij}\)；否则路径分解为 i→k→j。
-
空间优化：因 \(D^{(k-1)}\) 用过即丢弃，可用原地更新（仅 \(\Theta(n^2)\) 空间）。
-
前驱矩阵 \(\Pi^{(k)}\)：与 D 同时构造；式 25.6/25.7 给出递推。
-
负环检测：若任意 \(d^{(n)}_{ii} < 0\)，则存在负环（\(v \to v\) 路径权为负）。
传递闭包（§25.2）：将每条边权赋 1 跑 Floyd-Warshall，若 \(d_{ij} < n\) 则 i 可达 j；或用布尔版本把 min 替 OR、+ 替 AND，时间同为 \(\Theta(n^3)\) 但常数更小。
When：稠密图的全源最短路径；同时求前驱矩阵；需要传递闭包；负环检测。
Example：CLRS 图 25.4 的 5 顶点图，逐轮展示 \(D^{(k)}\) 与 \(\Pi^{(k)}\)；5 轮后 \(D^{(5)}\) 即最短路径权重。
25.4 Johnson 算法
What：用 Bellman-Ford 求势函数 \(h(v)\)，重赋权使所有边权非负，再对每个顶点跑 Dijkstra；总时间 \(O(V^2 \lg V + VE)\)；含负环则返回 FALSE。
Why：Dijkstra 在非负权时是单源最优；重赋权把负权图转为非负权图——这是「用最快算法处理最坏输入」的关键技巧。
How：
JOHNSON(G, w)：
-
加虚拟源 \(s'\)，对所有 \(v \in V\) 加边 \((s',v)\) 权 0。
-
if BELLMAN-FORD(G', w, s') == FALSE: return "negative cycle"
-
for each \(v \in V\): \(h(v) = \delta(s',v)\)
-
for each edge \((u,v) \in E\): \(\hat{w}(u,v) = w(u,v) + h(u) - h(v)\)
-
for each \(u \in V\): // V 次 Dijkstra
-
run DIJKSTRA(G, \hat{w}, u) 得到 \(\hat{\delta}(u, \cdot)\)
-
for each \(v \in V\): \(d_{uv} = \hat{\delta}(u,v) + h(v) - h(u)\)
-
重赋权性质（引理 25.1）：
-
\(\hat{w}(p) = w(p) + h(u) - h(v)\)，故 \(p\) 是否最短路径不变。
-
取 \(h(v) = \delta(s',v)\) 时，对任何边 \((u,v)\)，\(\hat{w}(u,v) = w(u,v) + \delta(s',u) - \delta(s',v)\)；由三角不等式 \(\delta(s',v) \leq \delta(s',u) + w(u,v)\)，故 \(\hat{w}(u,v) \geq 0\)。
-
负环检测等价：BELLMAN-FORD 返回 FALSE ⟺ 有负环。
When：稀疏图（\(E \ll V^2\)）的全源最短路径；图含负权边但无负环。
Example：稀疏社交网络（V=10000, E=50000）：Floyd-Warshall 需要 \(O(10^{12})\)，Johnson 只需 \(O(5 \times 10^5 \lg 10^4 + 5 \times 10^4)\) ≈ \(O(10^7)\)。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 25 章 全源最短路径))
问题形式化
权矩阵W
前驱矩阵Π
δ(i,j)
矩阵乘法法
DP递推
重复平方
O(V³lgV)
Floyd-Warshall
中间顶点DP
Θ(V³)
传递闭包
前驱构造
负环检测
Johnson算法
虚拟源
势函数h
重赋权非负
V次Dijkstra
稀疏图最优
算法对比
稠密选Floyd
稀疏选Johnson
含负权用Bellman五、重点与易错点
-
全源 vs 单源：单源（第 24 章）从 s 出发求到所有 v；全源求每对 (u,v)。单源算法跑 V 次可解全源，但不是最优。
-
邻接矩阵 vs 邻接表：本章除 §25.3 外用邻接矩阵，§25.3 用邻接表。矩阵便于 DP 索引；邻接表节省空间。
-
§25.1 的同构对照：EXTEND-SHORTEST-PATHS 是矩阵乘法的「算子替换」——min ↔ +, + ↔ ×, +∞ ↔ 0。这一对应不是巧合而是「(min, +) 半环」的体现。
-
重复平方的封闭性：\(W^{2^k} = W^{2^{k-1}} \circ W^{2^{k-1}}\)（算子替换意义下的乘法）；故 \(\lceil \lg(n-1) \rceil\) 次扩展即可达到 \(W^{n-1}\)。
-
Floyd-Warshall 的阶段变量是「中间顶点集合大小」，不是「边数」——这与 §25.1 不同；理解这一点是掌握 FW 的关键。
-
Floyd-Warshall 原地更新正确（CLRS 25.2-4）：因新值 \(d_{ik} / d_{kj}\) 是 k-1 轮的值，而当前轮内 (i, j) 的更新与 (i, k)/(k, j) 的更新无依赖关系（数组的同一位置会被 k 轮内多次更新但均收敛到正确值）。
-
前驱矩阵 \(\Pi\) 的正确性（CLRS 25.2-3）：需证明 \(\Pi^{(k)}\) 对应的前驱子图 \(G_{\pi,i}\) 是最短路径树——证明 \(\pi^{(k)}_{ij} = l\) 蕴含 \(d^{(k)}_{ij} \geq d^{(k)}_{il} + w_{lj}\)。
-
负环检测的两种方式：Floyd-Warshall 中看对角线 \(d^{(n)}_{ii} < 0\)；Johnson 看 Bellman-Ford 是否返回 FALSE。两者等价。
-
重赋权的「势」字来源：\(h(v)\) 物理上类比电势；\(\hat{w}(u,v) = w(u,v) + h(u) - h(v)\) 类比「电势差 = 实际值 + 起点电势 - 终点电势」。
-
三角不等式是重赋权非负的关键：\(\hat{w}(u,v) = w(u,v) + \delta(s',u) - \delta(s',v) \geq 0\) 由三角不等式直接推出；故 Dijkstra 可用。
-
Johnson 不适用含负环图：Bellman-Ford 检测出负环即停止；负环导致 \(\delta(s',v) = -\infty\)，无法定义 \(h(v)\)。
-
实践中算法选择：稠密图用 Floyd-Warshall（常数小）；稀疏图用 Johnson（理论最优）；非负权稀疏图用 V 次 Dijkstra。
-
与第 24 章的关系：Johnson 是「用 Bellman-Ford 求势」+「V 次 Dijkstra」的组合——前者代价 \(O(VE)\)（一次），后者代价 \(O(V \cdot (V \lg V + E)) = O(V^2 \lg V + VE)\)（V 次）；合计 \(O(V^2 \lg V + VE)\)。
-
与第 26 章的衔接：最短路径树是最大流（第 26 章）的残量网络基础；Johnson 的重赋权思想在网络流的费用调整中亦有应用。