Johnson 算法求解稀疏图中所有顶点对最短路径问题
1. 问题描述
在有向加权图中，我们希望求出所有顶点对之间的最短路径长度。
- 图可能含有负权边，但不能有负权环（否则最短路径无意义）。
- 顶点数为 \(V\)，边数为 \(E\)。
- 图的规模可能是稀疏的（即 \(E\) 与 \(V\) 同数量级或更小）。
已知的经典算法：
- Floyd-Warshall：\(O(V^3)\) 时间，适合稠密图，但不利用稀疏性。
- 对每个顶点运行一次 Dijkstra：若边权全为非负，总复杂度 \(O(V E \log V)\)；但若有负权边，Dijkstra 不能直接使用。
Johnson 算法的核心思想：通过一次重赋权（reweighting）消除负权边，然后在修改后的图上对每个顶点运行一次 Dijkstra，从而在稀疏图上获得比 Floyd-Warshall 更优的时间复杂度。
2. 算法步骤
Johnson 算法分为两步：
步骤 1：添加虚拟顶点并计算势能（Potentials）
-
在原图 \(G = (V, E)\) 的基础上，新增一个虚拟顶点 \(s\)，从 \(s\) 到原图中每个顶点 \(v\) 添加一条有向边，权重为 0。
新图记为 \(G' = (V \cup \{s\}, E')\)。
（这样保证从 \(s\) 到任意顶点可达，且无负权环时，从 \(s\) 出发的最短路径存在。） -
在 \(G'\) 上运行 Bellman-Ford 算法，以 \(s\) 为源点，求出从 \(s\) 到每个顶点 \(v\) 的最短路径长度 \(h(v)\)。
- 如果 Bellman-Ford 检测到负权环，算法终止（原图存在负权环，所有顶点对最短路径无解）。
- 否则，得到一组值 \(h(v)\)，称为顶点 \(v\) 的“势能”。
步骤 2：重赋权（消除负权）
对原图 \(G\) 中的每一条边 \((u, v)\)，权重为 \(w(u, v)\)，定义新的权重：
\[\hat{w}(u, v) = w(u, v) + h(u) - h(v) \]
性质：
- 新权重 \(\hat{w}(u, v)\) 保证非负（由三角不等式 \(h(v) \le h(u) + w(u, v)\) 可得）。
- 对于任意路径 \(p = (v_0, v_1, \dots, v_k)\)，有：
\[ \hat{w}(p) = w(p) + h(v_0) - h(v_k) \]
因此，路径之间的长度比较顺序不变（只是所有路径长度同时加上起点势能、减去终点势能），从而最短路径的结构不变。
步骤 3：在新图上运行 Dijkstra
- 对原图每个顶点 \(u\)：
- 以 \(u\) 为源点，在权重为 \(\hat{w}\) 的图上运行一次 Dijkstra 算法，得到从 \(u\) 到所有顶点 \(v\) 的新图最短路径距离 \(\hat{d}(u, v)\)。
- 将结果转换回原图权重：
\[ d(u, v) = \hat{d}(u, v) - h(u) + h(v) \]
- 输出所有 \(d(u, v)\) 即为原图所有顶点对最短路径长度。
3. 正确性分析
- 非负权重保证：
由 Bellman-Ford 的结果，对任意边 \((u, v)\)：
\[ h(v) \le h(u) + w(u, v) \quad\Rightarrow\quad \hat{w}(u, v) = w(u, v) + h(u) - h(v) \ge 0 \]
因此 Dijkstra 可以正确运行。
- 路径等价：
对任意路径 \(p\) 从 \(u\) 到 \(v\)：
\[ \hat{w}(p) = \sum_{i=0}^{k-1} [w(v_i, v_{i+1}) + h(v_i) - h(v_{i+1})] = w(p) + h(u) - h(v) \]
所以路径长度的排序完全相同，最短路径对应。
4. 时间复杂度
- 步骤 1（Bellman-Ford）：\(O(VE)\)
- 步骤 3（V 次 Dijkstra）：
- 若用二叉堆实现 Dijkstra，每次 \(O(E \log V)\)，总 \(O(VE \log V)\)
- 若用斐波那契堆，可降到 \(O(VE + V^2 \log V)\)
- 总复杂度：\(O(VE \log V)\) 在稀疏图（\(E = O(V)\)）时约为 \(O(V^2 \log V)\)，优于 Floyd-Warshall 的 \(O(V^3)\)。
5. 举例说明
假设原图有三个顶点 \(\{1,2,3\}\)：
- 边：\(1\to2: -2,\quad 2\to3: -1,\quad 3\to1: 4\)（无负权环）。
步骤 1：
加顶点 0，边 \(0\to1:0,\;0\to2:0,\;0\to3:0\)。
Bellman-Ford 从 0 开始：
- \(h(0)=0\)
- 迭代得 \(h(1)=0,\; h(2)=-2,\; h(3)=-3\)。
步骤 2：重赋权
原边 \(1\to2: -2\) → \(\hat{w}(1,2) = -2 + 0 - (-2) = 0\)
\(2\to3: -1\) → \(\hat{w} = -1 + (-2) - (-3) = 0\)
\(3\to1: 4\) → \(\hat{w} = 4 + (-3) - 0 = 1\)
新图无负权。
步骤 3：
对每个顶点运行 Dijkstra（以顶点 1 为例）：
- 新图中 1 到 2 距离 0，到 3 距离 0（路径 1→2→3）。
- 还原：\(d(1,2) = 0 - 0 + (-2) = -2\)；\(d(1,3) = 0 - 0 + (-3) = -3\)。
其他同理。
6. 总结
Johnson 算法的优点：
- 允许图中有负权边（无负权环）。
- 在稀疏图中比 Floyd-Warshall 更高效。
- 结合了 Bellman-Ford 的通用性和 Dijkstra 的高效性。