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

题目描述
给定一个可能包含负权边但不含负权环的稀疏有向图，要求计算图中所有顶点对之间的最短路径距离。稀疏图意味着边的数量相对较少（通常与顶点数量近似），因此我们需要一个能高效处理这种情况的算法。

解题过程
Johnson 算法结合了 Bellman-Ford 和 Dijkstra 算法的优势，通过重赋权技术消除负权边，从而允许在所有顶点上运行 Dijkstra 算法。以下是详细步骤：

1. 添加虚拟顶点并初始化

   • 创建一个新顶点 \(s\)，并添加从 \(s\) 到图中所有原顶点的边，这些边的权重设为 0。
   • 目标：通过这个虚拟顶点计算一个势能函数（也称为“高度”或“修正值”）。

2. 运行 Bellman-Ford 算法

   • 以 \(s\) 为源点，运行 Bellman-Ford 算法计算从 \(s\) 到所有原顶点的最短路径 \(h(v)\)。
   • 如果检测到负权环，算法终止（但题目已假设无负权环）。
   • 这里的 \(h(v)\) 将作为势能函数，用于调整边的权重。

3. 重赋权（消除负权边）

   • 对原图中每条边 \((u, v)\)，计算新的权重：

\[ \hat{w}(u, v) = w(u, v) + h(u) - h(v) \]

• 关键性质：新图中所有边的权重 \(\hat{w}(u, v)\) 均为非负，且重赋权不改变最短路径（仅调整路径长度的一致性）。

4. 在所有顶点上运行 Dijkstra 算法

   • 对每个原顶点 \(u\)，以其为源点在新图中运行 Dijkstra 算法，计算所有顶点 \(v\) 基于新权重的距离 \(\hat{d}(u, v)\)。

5. 还原实际最短路径距离

   • 将调整后的距离还原为实际距离：

\[ d(u, v) = \hat{d}(u, v) - h(u) + h(v) \]

• 最终得到的 \(d(u, v)\) 即为原图中从 \(u\) 到 \(v\) 的最短路径距离。

为什么有效？

• 势能函数 \(h(v)\) 通过 Bellman-Ford 计算，确保重赋权后边权非负，从而允许使用更高效的 Dijkstra 算法。
• 稀疏图中，Dijkstra 算法使用斐波那契堆或优先队列时复杂度为 \(O(V \log V + E)\)，整体复杂度为 \(O(VE + V^2 \log V)\)，在稀疏图（\(E \approx V\)）中优于 Floyd-Warshall 的 \(O(V^3)\)。

通过以上步骤，Johnson 算法高效解决了含负权边的稀疏图中所有顶点对的最短路径问题。