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

题目描述：
Johnson 算法是一种用于求解稀疏图中所有顶点对最短路径的高效算法。它结合了 Bellman-Ford 算法和 Dijkstra 算法的优势，特别适用于边数相对较少的稀疏图。该算法通过重赋权技术消除负权边，使得可以在修改后的图上安全地使用 Dijkstra 算法，从而获得所有顶点对之间的最短路径。

解题过程：

1. 问题分析

   • 在稀疏图中，直接对每个顶点运行 Dijkstra 算法（使用二叉堆）的时间复杂度为 O(V(E + V log V))，但 Dijkstra 不能处理负权边。
   • 如果使用 Floyd-Warshall 算法，时间复杂度为 O(V^3)，在稀疏图中效率较低。
   • Johnson 算法通过重赋权技术消除负权边，使得所有边权非负，从而可以安全使用 Dijkstra 算法。

2. 算法步骤
   a. 添加虚拟顶点

   • 在原有图 G 中添加一个新的顶点 s，并添加从 s 到所有原顶点的边，边权为 0。
   • 形成新图 G' = (V ∪ {s}, E ∪ {(s, v) | v ∈ V, w(s, v) = 0})。

   b. 运行 Bellman-Ford 算法

   • 以新顶点 s 为源点，在 G' 上运行 Bellman-Ford 算法，计算从 s 到所有顶点的最短距离 h(v)。
   • 如果检测到负权环，算法终止（原图存在负权环，无法求最短路径）。
   • 否则，得到一组势能值 h(v)，这些值将用于重赋权。

   c. 重赋权边

   • 对原图 G 中的每条边 (u, v)，定义新的边权：
     w'(u, v) = w(u, v) + h(u) - h(v)
   • 这一操作确保所有新边权 w'(u, v) ≥ 0，且保持最短路径结构。

   d. 运行 Dijkstra 算法

   • 对每个顶点 u ∈ V，在重赋权后的图上以 u 为源点运行 Dijkstra 算法，计算从 u 到所有顶点 v 的距离 d'(u, v)。

   e. 还原实际距离

   • 将重赋权后的距离转换回原图距离：
     d(u, v) = d'(u, v) - h(u) + h(v)

3. 关键原理详解
   a. 势能函数 h(v) 的作用

   • h(v) 是从虚拟顶点 s 到顶点 v 的最短距离。
   • 根据三角不等式，对于任意边 (u, v)，有 h(v) ≤ h(u) + w(u, v)。
   • 因此 w'(u, v) = w(u, v) + h(u) - h(v) ≥ 0。

   b. 路径保持性证明

   • 对于任意路径 p = (v₀, v₁, ..., vₖ)，有：
     w'(p) = w(p) + h(v₀) - h(vₖ)
   • 因此路径的权重变化只与起点和终点有关，不影响路径的相对比较。

4. 复杂度分析

   • 添加虚拟顶点和边：O(V)
   • Bellman-Ford 算法：O(VE)
   • 重赋权所有边：O(E)
   • V 次 Dijkstra 算法（使用二叉堆）：O(V(E + V log V))
   • 总复杂度：O(VE + V² log V)
   • 在稀疏图（E = O(V)）中，这优于 Floyd-Warshall 的 O(V³)。

5. 应用场景

   • 稀疏图中需要计算所有顶点对最短路径
   • 图中存在负权边但不含负权环
   • 需要频繁查询任意两点间最短路径的场景

这个算法巧妙地将两种经典算法结合，既处理了负权边问题，又在稀疏图中保持了较高的效率，是图论中一个优雅而实用的解决方案。