Johnson 算法求稀疏图中所有顶点对最短路径

题目描述
给定一个可能包含负权边但不包含负权环的稀疏有向图，要求计算图中所有顶点对之间的最短路径距离。稀疏图是指边数 |E| 远小于顶点数 |V| 的平方（即 |E| << |V|²）的图。Johnson 算法结合了 Bellman-Ford 算法和 Dijkstra 算法，能够高效处理稀疏图中的所有顶点对最短路径问题，即使图中存在负权边。

解题过程

步骤1：理解问题核心与挑战

• 在稀疏图中，Floyd-Warshall 算法（O(|V|³)）效率较低
• Dijkstra 算法不能直接处理负权边
• Bellman-Ford 算法对每个顶点运行一次的时间复杂度为 O(|V|²|E|)，在稀疏图中不够高效
• Johnson 算法的关键思路：通过重新赋权消除负权边，然后使用高效的 Dijkstra 算法

步骤2：算法框架
Johnson 算法包含三个主要阶段：

1. 添加虚拟顶点和边
2. 使用 Bellman-Ford 算法计算势能函数
3. 对每个顶点运行 Dijkstra 算法

步骤3：添加虚拟顶点

• 在原有图 G = (V, E) 的基础上，添加一个新的顶点 q
• 从 q 向原图中每个顶点 v ∈ V 添加一条权重为 0 的有向边
• 形成新图 G' = (V', E')，其中 V' = V ∪ {q}，E' = E ∪ {(q, v) | v ∈ V}

这个步骤的数学表示：

对于每个顶点 v ∈ V，添加边 (q, v) 且 w(q, v) = 0

步骤4：计算势能函数

• 在新图 G' 上，以 q 为源点运行 Bellman-Ford 算法
• 计算从 q 到每个顶点 v 的最短路径距离 h(v)
• 函数 h: V → ℝ 称为势能函数

关键性质验证：

• 如果原图 G 不含负权环，则 G' 也不含负权环
• Bellman-Ford 算法能够正确计算 h(v) 值
• 时间复杂度：O(|V||E|)

步骤5：重新赋权变换
对于原图中的每条边 (u, v) ∈ E，定义新的权重：

ŵ(u, v) = w(u, v) + h(u) - h(v)

这个变换的关键性质：

1. 保持最短路径：任意两点间的最短路径在变换前后保持不变
2. 非负权重：变换后的图中所有边权非负

证明性质2：
根据三角不等式，对于原图中的最短路径有：
h(v) ≤ h(u) + w(u, v)
因此 ŵ(u, v) = w(u, v) + h(u) - h(v) ≥ 0

步骤6：运行 Dijkstra 算法

• 在重新赋权后的图上，对每个顶点 s ∈ V 运行 Dijkstra 算法
• 计算从 s 到所有其他顶点的最短路径距离 δ̂(s, v)

步骤7：还原实际距离
将变换后的距离还原为实际距离：

δ(s, v) = δ̂(s, v) - h(s) + h(v)

验证正确性：
对于任意路径 p = v₀ → v₁ → ... → vₖ，有：
ŵ(p) = w(p) + h(v₀) - h(vₖ)
因此 δ̂(s, v) = δ(s, v) + h(s) - h(v)

步骤8：复杂度分析

• 添加虚拟顶点：O(|V|)
• Bellman-Ford：O(|V||E|)
• |V| 次 Dijkstra：
  • 使用二叉堆：O(|V||E|log|V|)
  • 使用斐波那契堆：O(|V|²log|V| + |V||E|)
• 总复杂度：O(|V||E|log|V|) 或 O(|V|²log|V| + |V||E|)

在稀疏图中（|E| = O(|V|)），Johnson 算法明显优于 Floyd-Warshall 算法。

步骤9：算法实现要点

1. 确保原图不含负权环
2. 仔细处理势能函数的计算
3. 在重新赋权时注意数值精度
4. 选择合适的优先队列实现 Dijkstra 算法

Johnson 算法通过巧妙的重新赋权技巧，将含负权边的最短路径问题转化为非负权问题，从而能够充分利用 Dijkstra 算法的高效性，在稀疏图中表现出优越的性能。