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

题目描述
给定一个可能包含负权边但不含负权环的稀疏有向图，如何高效计算所有顶点对之间的最短路径？直接应用Floyd-Warshall算法的时间复杂度为O(V³)，在稀疏图（边数E远小于V²）中效率较低。Johnson算法通过结合Bellman-Ford和Dijkstra算法，将时间复杂度优化到O(V² log V + VE)，在稀疏图中显著优于Floyd-Warshall。

解题过程

1. 问题分析

   • 目标：计算图中每一对顶点(u, v)之间的最短路径距离。
   • 挑战：负权边使得Dijkstra算法无法直接应用；稀疏图中Floyd-Warshall算法浪费计算资源。
   • 关键思路：通过重赋权技术消除负权边，使Dijkstra算法可重复使用。

2. 重赋权原理

   • 定义新权重：对于边(u, v)，设新权重w'(u, v) = w(u, v) + h(u) - h(v)。
   • 性质：若h满足三角不等式，新图中所有边权非负，且最短路径结构不变（路径相对顺序保持一致）。

3. 算法步骤
   步骤1：添加虚拟源点

   • 向图中添加一个新顶点s，并添加s到所有原顶点的边，权重为0。
   • 使用Bellman-Ford算法计算从s到所有顶点的最短路径距离h(v)。若检测到负权环，算法终止。

   步骤2：重赋权边

   • 对于每条边(u, v)，计算新权重w'(u, v) = w(u, v) + h(u) - h(v)。
   • 数学验证：由于h(v)是最短路径距离，满足h(v) ≤ h(u) + w(u, v)，因此w'(u, v) ≥ 0。

   步骤3：运行V次Dijkstra算法

   • 对每个顶点u，在新图上运行Dijkstra算法，得到所有顶点v到u的最短距离d'(u, v)。
   • 还原实际距离：d(u, v) = d'(u, v) - h(u) + h(v)。

4. 复杂度分析

   • Bellman-Ford：O(VE)
   • V次Dijkstra：使用斐波那契堆时每次O(V log V + E)，总计O(V² log V + VE)
   • 总复杂度：O(V² log V + VE)，稀疏图（E ≈ V）时接近O(V² log V)。

实例演示
考虑包含顶点{A, B, C}的图，边权：A→B=-1, B→C=2, C→A=-2。

1. 添加虚拟源点s，边s→A/B/C=0。
2. Bellman-Ford计算h(A)=0, h(B)=-1, h(C)=1（路径s→B→C）。
3. 重赋权：A→B: -1 + 0 - (-1) = 0; B→C: 2 + (-1) - 1 = 0; C→A: -2 + 1 - 0 = -1 → 修正后为0。
4. 新图无负权，运行Dijkstra得最短路径后还原距离。

关键点总结

• Johnson算法通过重赋权巧妙利用Dijkstra的高效性。
• 虚拟源点确保h函数满足三角不等式。
• 稀疏图中优势明显，但稠密图（E≈V²）时不如Floyd-Warshall简单直接。