Johnson 算法求解稀疏图的全源最短路径问题 题目描述 Johnson 算法是一种用于求解 稀疏图 中 所有顶点对之间最短路径 的高效算法。它结合了 Bellman-Ford 算法和 Dijkstra 算法的优点，适用于 包含负权边但不含负权环 的有向图。算法的核心思想是通过 重赋权 （reweighting）技术，消除图中的负权边，使得所有边的权值变为非负，从而可以在新图上对每个顶点运行一次 Dijkstra 算法来求解全源最短路径，最终将结果转换回原图的实际最短路径。与 Floyd-Warshall 算法（O(V³) 时间复杂度）相比，在稀疏图（边数 E 远小于 V²）中，Johnson 算法的时间复杂度为 O(V E log V)，通常更为高效。 解题过程循序渐进讲解 步骤 1：理解问题输入与目标 输入：一个 有向图 G = (V, E)，其中 V 是顶点集合，E 是边集合，每条边 (u, v) 有一个权值 w(u, v)（可以是正数、负数或零）。 假设：图中 不存在负权环 （即从任一顶点出发，经过若干边回到自身，总权值不能为负）。 目标：计算图中 每一对顶点 (u, v) 之间的最短路径距离。 步骤 2：为什么不能直接使用 Dijkstra 或 Floyd-Warshall？ Dijkstra 算法要求所有边权 非负 ，如果图中存在负权边，直接使用会得到错误结果。 Floyd-Warshall 算法可以处理负权边，但时间复杂度为 O(V³)，在稀疏图中不够高效（例如 V=1000, E=3000 时，V³=10^9，而 V E log V ≈ 10^7）。 因此，我们需要一种能利用 Dijkstra 算法的高效性，同时能处理负权边的方法。 步骤 3：Johnson 算法的核心思路 算法通过以下三步实现： 添加虚拟源点 ：在图 G 中添加一个 新顶点 s ，并从 s 向图中所有原顶点 v ∈ V 添加一条权值为 0 的有向边 (s, v)。得到新图 G'。 计算顶点势能 ：在 G' 上运行 Bellman-Ford 算法 ，以 s 为源点，计算从 s 到每个原顶点 v 的最短距离 h[ v]。如果检测到负权环，则算法终止（原图存在负权环，无解）。否则，h[ v ] 将作为顶点 v 的“势能”（potential）。 重赋权边 ：对于原图 G 中的每条边 (u, v)，定义 新的边权 w'(u, v) = w(u, v) + h[ u] - h[ v ]。 在新图上运行 Dijkstra ：对于每个原顶点 u ∈ V，以 u 为源点，在 新图 G 上（边权为 w'） 运行一次 Dijkstra 算法 ，计算从 u 到所有其他顶点 v 在新图上的最短距离 d'(u, v)。 还原实际距离 ：原图 G 中从 u 到 v 的实际最短距离 d(u, v) = d'(u, v) - h[ u] + h[ v ]。 步骤 4：为什么重赋权能消除负权边？ 关键性质：对于原图中的 任意一条路径 P = (v₀, v₁, ..., vₖ)，新旧边权的关系满足： Σ w'(vᵢ, vᵢ₊₁) = Σ w(vᵢ, vᵢ₊₁) + h[ v₀] - h[ vₖ ]。 由于 h[ v] 是 Bellman-Ford 计算出的最短距离，满足 三角不等式 ：h[ v] ≤ h[ u] + w(u, v)，移项得 w(u, v) + h[ u] - h[ v] ≥ 0，即 w'(u, v) ≥ 0 。 因此，新图 G 中所有边权 w' 均为非负，可以使用 Dijkstra 算法。 步骤 5：为什么还原公式是正确的？ 在新图上，从 u 到 v 的任意路径 P 满足：路径总权值 w'(P) = w(P) + h[ u] - h[ v ]。 因此，新图上的最短路径 P* 对应原图的最短路径，且 d'(u, v) = d(u, v) + h[ u] - h[ v ]。 移项即得还原公式：d(u, v) = d'(u, v) - h[ u] + h[ v ]。 步骤 6：详细步骤与示例 假设有一个有向图 G 包含 4 个顶点 {1, 2, 3, 4}，边权如下（含负权边）： (1→2, 3), (1→3, 8), (1→4, -4), (2→4, 7), (2→1, 4), (3→2, -5), (4→3, 2), (4→1, 6)。 添加虚拟源点 s ：添加 s 和边 (s→1, 0), (s→2, 0), (s→3, 0), (s→4, 0)。 Bellman-Ford 计算 h[ v] ：以 s 为源点，计算后得到（示例结果，实际需运行算法）： h[ 1]=0, h[ 2]=-1, h[ 3]=-5, h[ 4 ]=-4。 重赋权 w' ：例如边 (1→2)：w'(1,2)=w(1,2)+h[ 1]-h[ 2 ]=3+0-(-1)=4。 计算所有边得到新边权（均为非负）： (1→2,4), (1→3,13), (1→4,0), (2→4,12), (2→1,5), (3→2,1), (4→3,11), (4→1,10)。 运行多次 Dijkstra ：以顶点 1 为源点，在新图上运行 Dijkstra，得到 d'(1,2)=4, d'(1,3)=11, d'(1,4)=0。 还原实际距离 ：d(1,2)=d'(1,2)-h[ 1]+h[ 2 ]=4-0+(-1)=3。 依次计算所有顶点对，得到全源最短路径距离矩阵。 步骤 7：时间复杂度分析 添加虚拟源点和运行 Bellman-Ford：O(V E)。 重赋权：O(E)。 V 次 Dijkstra：使用二叉堆优先队列时，每次 O(E log V)，总共 O(V E log V)。 总复杂度：O(V E log V)（稀疏图 E=O(V) 时，约为 O(V² log V)，优于 Floyd-Warshall 的 O(V³)）。 步骤 8：总结 Johnson 算法通过 势能转换 将负权边转化为非负边，从而能够利用高效的 Dijkstra 算法求解全源最短路径。它特别适合 边数相对较少 的稀疏图，且能处理 负权边 （只要没有负权环）。