Johnson 算法求解稀疏图中所有顶点对最短路径
字数 2829 2025-12-15 10:42:01

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

题目描述
给你一个包含 n 个顶点和 m 条边的有向图，图中边的权重可能为负数，但图中不存在负权环。请你计算出图中所有顶点对之间的最短路径距离。即，对于每一对顶点 (i, j)，输出从 i 到 j 的最短路径长度。如果 i 无法到达 j，则距离为无穷大。要求算法的时间复杂度在稀疏图（m = O(n)）上优于直接对每个顶点运行 Dijkstra 算法（使用二叉堆时总复杂度 O(n² log n)），也优于 Floyd-Warshall 算法的 O(n³)。

解题思路
直接思路是：

  1. 对每个顶点运行 Dijkstra 算法（需非负权重），但图中有负权边，不能直接用。
  2. 用 Floyd-Warshall 算法（O(n³)），在稀疏图上不够高效。
    Johnson 算法的核心思想是：通过引入一个“势能函数”对边权进行重新赋值，使得所有权重变为非负，但保持最短路径结构不变，然后对每个顶点运行一次 Dijkstra 算法。
    关键步骤：
  3. 增加一个虚拟源点，到所有顶点连一条权重为 0 的边，用 Bellman-Ford 算法计算从该源点到所有顶点的最短距离 h(v)（即势能）。
  4. 利用 h(v) 对原图每条边 (u, v) 的权重 w(u, v) 进行重新赋值：w'(u, v) = w(u, v) + h(u) - h(v)。可以证明 w'(u, v) ≥ 0。
  5. 对每个顶点 s，在权重 w' 的图上运行 Dijkstra 算法，得到距离 d'(s, v)，再还原为原图上的最短距离 d(s, v) = d'(s, v) - h(s) + h(v)。
    总复杂度：O(nm)（Bellman-Ford） + n × O(m log n)（n 次 Dijkstra，使用二叉堆） = O(nm log n)，在稀疏图（m = O(n)）上为 O(n² log n)，优于 Floyd-Warshall 的 O(n³)。

逐步讲解

步骤1：理解问题与挑战
我们需要所有顶点对之间的最短路径。

  • 如果权重都非负，可对每个顶点运行 Dijkstra（二叉堆实现），总时间 O(n(m + n) log n) ≈ O(n² log n)（当 m = O(n) 时）。
  • 但如果有负权边，Dijkstra 不能直接使用。
  • Floyd-Warshall 总是可以，但 O(n³) 在稀疏图上较慢。
    Johnson 算法结合了 Bellman-Ford（处理负权）和 Dijkstra（高效求单源最短路），并通过重赋权消除负权。

步骤2：引入势能与重赋权原理
假设我们给每个顶点 v 分配一个势能 h(v)。对每条边 (u, v)，定义新的权重：

\[w'(u, v) = w(u, v) + h(u) - h(v) \]

性质1：重赋权后，任意路径 p = (v₁, v₂, ..., vₖ) 的长度变化为：
原长度 w(p) = Σ w(vᵢ, vᵢ₊₁)
新长度 w'(p) = Σ [w(vᵢ, vᵢ₊₁) + h(vᵢ) - h(vᵢ₊₁)] = w(p) + h(v₁) - h(vₖ)
这意味着，路径长度只改变了起点和终点的势能差，因此任意两点间的最短路径在新权重下保持不变（因为所有从 u 到 v 的路径都增加了 h(u) - h(v)）。

步骤3：使新权重非负的条件
我们希望 w'(u, v) ≥ 0 对所有边成立。
即 w(u, v) + h(u) - h(v) ≥ 0
整理得：h(v) ≤ h(u) + w(u, v)
这正是最短路径的三角不等式形式：如果 h(v) 是从某个源点 s 到 v 的最短距离，那么该不等式成立。
因此，如果我们能求出一组势能 h(v)，使得对于每条边 (u, v)，h(v) ≤ h(u) + w(u, v)，则重赋权后所有边权非负。
这等价于以某个虚拟源点 s 为起点，到所有顶点的最短距离满足此性质。

步骤4：计算势能 h(v)
我们在原图的基础上增加一个新顶点 s，并从 s 向原图每个顶点 v 连一条权重为 0 的有向边。
然后以 s 为源点，运行 Bellman-Ford 算法（因为可能有负权边），求出 s 到每个顶点 v 的最短距离，记为 h(v)。
由于原图没有负权环，新图（加入 s 后）也没有负权环，所以 Bellman-Ford 能正确求出最短距离，并且满足：
对于原图中任意边 (u, v)，有 h(v) ≤ h(u) + w(u, v)（因为 h(v) 是 s 到 v 的最短距离，h(u) + w(u, v) 是一条从 s 到 v 的路径，长度不会更短）。
因此，h(v) 就是我们需要的势能函数。

步骤5：重赋权与运行 Dijkstra
得到 h(v) 后，对原图的每条边 (u, v)，计算新权重：
w'(u, v) = w(u, v) + h(u) - h(v)
由步骤4的结论，w'(u, v) ≥ 0。
然后，对原图的每个顶点 u，以 u 为源点，在权重 w' 的图上运行 Dijkstra 算法（因为 w' 非负），得到从 u 到各顶点 v 在新权重下的最短距离 D'[u][v]。

步骤6：还原为原图最短距离
由步骤2的公式：对于从 u 到 v 的任何路径，新长度 w'(p) = w(p) + h(u) - h(v)。
最短路径也满足此关系，因此：
原图最短距离 D[u][v] = D'[u][v] - h(u) + h(v)。
注意：如果 D'[u][v] 是无穷大（不可达），则 D[u][v] 也是无穷大。

步骤7：复杂度分析

  • 加入虚拟源点，运行 Bellman-Ford：O(nm)。
  • 计算新权重 w'：O(m)。
  • 运行 n 次 Dijkstra（二叉堆实现）：O(n(m + n) log n) ≈ O(nm log n)（若 m ≥ n）。
    总复杂度 O(nm log n)，在稀疏图 m = O(n) 时，为 O(n² log n)，优于 Floyd-Warshall 的 O(n³)。

步骤8：边界情况与实现细节

  • 如果 Bellman-Ford 检测到负权环（虽然题目保证没有），则算法停止。
  • 由于 h(v) 可能很大，在计算 w' 和还原 D 时可能溢出，需注意使用足够大的数据类型。
  • 存储所有顶点对距离需要 O(n²) 空间。
  • 实际实现时，不必显式构造新图，只需在 Dijkstra 中使用 w' 的计算函数即可。

总结
Johnson 算法巧妙地利用势能转换，将含负权但无负权环的图转换为非负权图，从而可应用高效的 Dijkstra 算法求所有顶点对最短路。它在稀疏图上比 Floyd-Warshall 更快，是解决此类问题的经典算法。

Johnson 算法求解稀疏图中所有顶点对最短路径 题目描述 给你一个包含 n 个顶点和 m 条边的有向图，图中边的权重可能为负数，但图中不存在负权环。请你计算出图中所有顶点对之间的最短路径距离。即，对于每一对顶点 (i, j)，输出从 i 到 j 的最短路径长度。如果 i 无法到达 j，则距离为无穷大。要求算法的时间复杂度在稀疏图（m = O(n)）上优于直接对每个顶点运行 Dijkstra 算法（使用二叉堆时总复杂度 O(n² log n)），也优于 Floyd-Warshall 算法的 O(n³)。 解题思路 直接思路是： 对每个顶点运行 Dijkstra 算法（需非负权重），但图中有负权边，不能直接用。 用 Floyd-Warshall 算法（O(n³)），在稀疏图上不够高效。 Johnson 算法的核心思想是： 通过引入一个“势能函数”对边权进行重新赋值，使得所有权重变为非负，但保持最短路径结构不变，然后对每个顶点运行一次 Dijkstra 算法 。 关键步骤： 增加一个虚拟源点，到所有顶点连一条权重为 0 的边，用 Bellman-Ford 算法计算从该源点到所有顶点的最短距离 h(v)（即势能）。 利用 h(v) 对原图每条边 (u, v) 的权重 w(u, v) 进行重新赋值：w'(u, v) = w(u, v) + h(u) - h(v)。可以证明 w'(u, v) ≥ 0。 对每个顶点 s，在权重 w' 的图上运行 Dijkstra 算法，得到距离 d'(s, v)，再还原为原图上的最短距离 d(s, v) = d'(s, v) - h(s) + h(v)。 总复杂度：O(nm)（Bellman-Ford） + n × O(m log n)（n 次 Dijkstra，使用二叉堆） = O(nm log n)，在稀疏图（m = O(n)）上为 O(n² log n)，优于 Floyd-Warshall 的 O(n³)。 逐步讲解 步骤1：理解问题与挑战 我们需要所有顶点对之间的最短路径。 如果权重都非负，可对每个顶点运行 Dijkstra（二叉堆实现），总时间 O(n(m + n) log n) ≈ O(n² log n)（当 m = O(n) 时）。 但如果有负权边，Dijkstra 不能直接使用。 Floyd-Warshall 总是可以，但 O(n³) 在稀疏图上较慢。 Johnson 算法结合了 Bellman-Ford（处理负权）和 Dijkstra（高效求单源最短路），并通过重赋权消除负权。 步骤2：引入势能与重赋权原理 假设我们给每个顶点 v 分配一个势能 h(v)。对每条边 (u, v)，定义新的权重： \[ w'(u, v) = w(u, v) + h(u) - h(v) \] 性质1：重赋权后，任意路径 p = (v₁, v₂, ..., vₖ) 的长度变化为： 原长度 w(p) = Σ w(vᵢ, vᵢ₊₁) 新长度 w'(p) = Σ [ w(vᵢ, vᵢ₊₁) + h(vᵢ) - h(vᵢ₊₁) ] = w(p) + h(v₁) - h(vₖ) 这意味着，路径长度只改变了起点和终点的势能差，因此任意两点间的最短路径在新权重下保持不变 （因为所有从 u 到 v 的路径都增加了 h(u) - h(v)）。 步骤3：使新权重非负的条件 我们希望 w'(u, v) ≥ 0 对所有边成立。 即 w(u, v) + h(u) - h(v) ≥ 0 整理得：h(v) ≤ h(u) + w(u, v) 这正是最短路径的三角不等式形式 ：如果 h(v) 是从某个源点 s 到 v 的最短距离，那么该不等式成立。 因此，如果我们能求出一组势能 h(v)，使得对于每条边 (u, v)，h(v) ≤ h(u) + w(u, v)，则重赋权后所有边权非负。 这等价于以某个虚拟源点 s 为起点，到所有顶点的最短距离满足此性质。 步骤4：计算势能 h(v) 我们在原图的基础上增加一个新顶点 s，并从 s 向原图每个顶点 v 连一条权重为 0 的有向边。 然后以 s 为源点，运行 Bellman-Ford 算法 （因为可能有负权边），求出 s 到每个顶点 v 的最短距离，记为 h(v)。 由于原图没有负权环，新图（加入 s 后）也没有负权环，所以 Bellman-Ford 能正确求出最短距离，并且满足： 对于原图中任意边 (u, v)，有 h(v) ≤ h(u) + w(u, v)（因为 h(v) 是 s 到 v 的最短距离，h(u) + w(u, v) 是一条从 s 到 v 的路径，长度不会更短）。 因此，h(v) 就是我们需要的势能函数 。 步骤5：重赋权与运行 Dijkstra 得到 h(v) 后，对原图的每条边 (u, v)，计算新权重： w'(u, v) = w(u, v) + h(u) - h(v) 由步骤4的结论，w'(u, v) ≥ 0。 然后， 对原图的每个顶点 u ，以 u 为源点，在权重 w' 的图上运行 Dijkstra 算法 （因为 w' 非负），得到从 u 到各顶点 v 在新权重下的最短距离 D'[ u][ v ]。 步骤6：还原为原图最短距离 由步骤2的公式：对于从 u 到 v 的任何路径，新长度 w'(p) = w(p) + h(u) - h(v)。 最短路径也满足此关系，因此： 原图最短距离 D[ u][ v] = D'[ u][ v ] - h(u) + h(v)。 注意：如果 D'[ u][ v] 是无穷大（不可达），则 D[ u][ v ] 也是无穷大。 步骤7：复杂度分析 加入虚拟源点，运行 Bellman-Ford：O(nm)。 计算新权重 w'：O(m)。 运行 n 次 Dijkstra（二叉堆实现）：O(n(m + n) log n) ≈ O(nm log n)（若 m ≥ n）。 总复杂度 O(nm log n)，在稀疏图 m = O(n) 时，为 O(n² log n)，优于 Floyd-Warshall 的 O(n³)。 步骤8：边界情况与实现细节 如果 Bellman-Ford 检测到负权环（虽然题目保证没有），则算法停止。 由于 h(v) 可能很大，在计算 w' 和还原 D 时可能溢出，需注意使用足够大的数据类型。 存储所有顶点对距离需要 O(n²) 空间。 实际实现时，不必显式构造新图，只需在 Dijkstra 中使用 w' 的计算函数即可。 总结 Johnson 算法巧妙地利用势能转换，将含负权但无负权环的图转换为非负权图，从而可应用高效的 Dijkstra 算法求所有顶点对最短路。它在稀疏图上比 Floyd-Warshall 更快，是解决此类问题的经典算法。