Dijkstra算法的应用：多源最短路径的Johnson算法
字数 2406 2025-12-12 05:56:19

Dijkstra算法的应用：多源最短路径的Johnson算法

1. 问题描述

Johnson算法用于求解带权有向图中所有顶点对之间的最短路径。它特别适合处理稀疏图（边数远少于完全图）且可能包含负权边（但不允许存在负权环）的情况。该算法结合了Bellman-Ford算法和Dijkstra算法，能高效解决全源最短路径问题。

2. 为什么需要Johnson算法？

  • 直接使用Dijkstra算法：如果图中有负权边，Dijkstra算法无法正确工作。
  • 直接使用Bellman-Ford算法：对每个顶点运行一次Bellman-Ford，时间复杂度为O(V²E)，对于稀疏图效率较低。
  • Floyd-Warshall算法：时间复杂度O(V³)，在稀疏图中不如Johnson算法高效。
  • Johnson算法的优势：通过重加权技术消除负权边，然后对所有顶点运行Dijkstra算法，在稀疏图中时间复杂度为O(VE log V)。

3. 算法核心思想

Johnson算法的核心是重加权（reweighting）：

  1. 添加虚拟源点：向图中添加一个新顶点s，并添加从s到所有原顶点的边，权重为0。
  2. 计算新权重：使用Bellman-Ford算法计算从s到所有原顶点的最短距离h(v)（称为势能函数）。
  3. 重加权所有边：对原图中每条边(u, v)，将权重w(u, v)更新为w'(u, v) = w(u, v) + h(u) - h(v)。
  4. 运行Dijkstra：对重加权后的图中每个顶点作为源点，运行Dijkstra算法。
  5. 恢复原始距离：将Dijkstra得到的最短路径距离还原为原始图中的距离。

4. 算法步骤详解

步骤1：添加虚拟源点

  • 创建一个新顶点s（索引为V，如果原图有V个顶点）。
  • 添加从s到所有原顶点v的边：权重为0。
  • 此时图有V+1个顶点。

步骤2：使用Bellman-Ford计算h(v)

  • 以s为源点运行Bellman-Ford算法。
  • 得到从s到每个顶点v的最短距离h(v)。
  • 关键性质：
    • 如果原图存在负权环，Bellman-Ford会检测到，算法终止。
    • 否则，对于所有边(u, v)，满足三角不等式：h(v) ≤ h(u) + w(u, v)。
    • 这意味着：w(u, v) + h(u) - h(v) ≥ 0。

步骤3：重加权所有边

  • 对原图中每条边(u, v)（不包括添加的边）：
    • 计算新权重：w'(u, v) = w(u, v) + h(u) - h(v)。
  • 为什么新权重非负？
    • 由三角不等式：w(u, v) + h(u) - h(v) ≥ 0。
    • 因此，重加权后的图没有负权边。

步骤4：运行Dijkstra算法

  • 对每个原顶点u（V个顶点）：
    • 以u为源点，在重加权后的图上运行Dijkstra算法。
    • 得到从u到所有其他顶点v的重加权距离d'(u, v)。

步骤5：恢复原始距离

  • 对每对顶点(u, v)：
    • 原始最短距离d(u, v) = d'(u, v) - h(u) + h(v)。
  • 为什么正确？
    • 设P是从u到v的一条路径。
    • 重加权后路径长度：w'(P) = Σ[w(e) + h(u_i) - h(u_{i+1})] = w(P) + h(u) - h(v)。
    • 因此，w(P) = w'(P) - h(u) + h(v)。
    • 最短路径在重加权前后保持不变。

5. 时间复杂度分析

  1. 添加虚拟源点：O(V)。
  2. Bellman-Ford算法：O(VE)。
  3. 重加权所有边：O(E)。
  4. V次Dijkstra算法：如果使用二叉堆，每次O((V+E) log V)，总共O(V(E+V) log V)。对于稀疏图（E=O(V)），约为O(V² log V)。
  5. 恢复原始距离：O(V²)。

总时间复杂度：O(VE log V)（使用二叉堆的Dijkstra）。对于稀疏图，优于Floyd-Warshall的O(V³)。

6. 实例演示

考虑有向图，顶点{A, B, C}，边：

  • A→B: -2
  • B→C: -1
  • C→A: 4
  • C→B: 3

步骤1：添加虚拟源点S，边S→A、S→B、S→C权重为0。

步骤2：运行Bellman-Ford，计算h(v)：

  • h(A)=0, h(B)=-2, h(C)=-3

步骤3：重加权：

  • A→B: -2 + 0 - (-2) = 0
  • B→C: -1 + (-2) - (-3) = 0
  • C→A: 4 + (-3) - 0 = 1
  • C→B: 3 + (-3) - (-2) = 2

步骤4：对每个顶点运行Dijkstra（重加权图无负权）：

  • 从A：d'(A,B)=0, d'(A,C)=0, d'(A,A)=0
  • 从B：d'(B,C)=0, d'(B,A)=1, d'(B,B)=0
  • 从C：d'(C,A)=1, d'(C,B)=2, d'(C,C)=0

步骤5：恢复原始距离：

  • d(A,B) = 0 - 0 + (-2) = -2
  • d(A,C) = 0 - 0 + (-3) = -3
  • d(B,A) = 1 - (-2) + 0 = 3
  • 等等...

7. 关键要点

  • 适用条件：无负权环的有向加权图。
  • 核心技巧：通过重加权消除负权边，使Dijkstra可用。
  • 优势：在稀疏图中，比直接V次Bellman-Ford或Floyd-Warshall更高效。
  • 空间复杂度：O(V²)存储所有顶点对距离。
  • 变体应用：可用于需要多次计算最短路径的场景，如网络路由协议。

8. 常见面试问题

  1. 为什么Johnson算法中重加权后的边权非负？
  2. 如果图中有负权环，Johnson算法如何处理？
  3. 比较Johnson算法与Floyd-Warshall算法的适用场景。
  4. 如何证明重加权不改变最短路径？
  5. 为什么选择添加虚拟源点而不是其他方法？
Dijkstra算法的应用：多源最短路径的Johnson算法 1. 问题描述 Johnson算法用于求解 带权有向图 中 所有顶点对 之间的 最短路径 。它特别适合处理 稀疏图 （边数远少于完全图）且可能包含 负权边 （但不允许存在负权环）的情况。该算法结合了Bellman-Ford算法和Dijkstra算法，能高效解决全源最短路径问题。 2. 为什么需要Johnson算法？ 直接使用Dijkstra算法 ：如果图中有负权边，Dijkstra算法无法正确工作。 直接使用Bellman-Ford算法 ：对每个顶点运行一次Bellman-Ford，时间复杂度为O(V²E)，对于稀疏图效率较低。 Floyd-Warshall算法 ：时间复杂度O(V³)，在稀疏图中不如Johnson算法高效。 Johnson算法的优势 ：通过 重加权 技术消除负权边，然后对所有顶点运行Dijkstra算法，在稀疏图中时间复杂度为O(VE log V)。 3. 算法核心思想 Johnson算法的核心是 重加权 （reweighting）： 添加虚拟源点 ：向图中添加一个新顶点s，并添加从s到所有原顶点的边，权重为0。 计算新权重 ：使用Bellman-Ford算法计算从s到所有原顶点的最短距离h(v)（称为势能函数）。 重加权所有边 ：对原图中每条边(u, v)，将权重w(u, v)更新为w'(u, v) = w(u, v) + h(u) - h(v)。 运行Dijkstra ：对重加权后的图中每个顶点作为源点，运行Dijkstra算法。 恢复原始距离 ：将Dijkstra得到的最短路径距离还原为原始图中的距离。 4. 算法步骤详解 步骤1：添加虚拟源点 创建一个新顶点s（索引为V，如果原图有V个顶点）。 添加从s到所有原顶点v的边：权重为0。 此时图有V+1个顶点。 步骤2：使用Bellman-Ford计算h(v) 以s为源点运行Bellman-Ford算法。 得到从s到每个顶点v的最短距离h(v)。 关键性质 ： 如果原图存在负权环，Bellman-Ford会检测到，算法终止。 否则，对于所有边(u, v)，满足 三角不等式 ：h(v) ≤ h(u) + w(u, v)。 这意味着：w(u, v) + h(u) - h(v) ≥ 0。 步骤3：重加权所有边 对原图中每条边(u, v)（不包括添加的边）： 计算新权重：w'(u, v) = w(u, v) + h(u) - h(v)。 为什么新权重非负？ 由三角不等式：w(u, v) + h(u) - h(v) ≥ 0。 因此，重加权后的图 没有负权边 。 步骤4：运行Dijkstra算法 对每个原顶点u（V个顶点）： 以u为源点，在重加权后的图上运行Dijkstra算法。 得到从u到所有其他顶点v的 重加权距离 d'(u, v)。 步骤5：恢复原始距离 对每对顶点(u, v)： 原始最短距离d(u, v) = d'(u, v) - h(u) + h(v)。 为什么正确？ 设P是从u到v的一条路径。 重加权后路径长度：w'(P) = Σ[ w(e) + h(u_ i) - h(u_ {i+1}) ] = w(P) + h(u) - h(v)。 因此，w(P) = w'(P) - h(u) + h(v)。 最短路径在重加权前后保持不变。 5. 时间复杂度分析 添加虚拟源点 ：O(V)。 Bellman-Ford算法 ：O(VE)。 重加权所有边 ：O(E)。 V次Dijkstra算法 ：如果使用二叉堆，每次O((V+E) log V)，总共O(V(E+V) log V)。对于稀疏图（E=O(V)），约为O(V² log V)。 恢复原始距离 ：O(V²)。 总时间复杂度 ：O(VE log V)（使用二叉堆的Dijkstra）。对于稀疏图，优于Floyd-Warshall的O(V³)。 6. 实例演示 考虑有向图，顶点{A, B, C}，边： A→B: -2 B→C: -1 C→A: 4 C→B: 3 步骤1 ：添加虚拟源点S，边S→A、S→B、S→C权重为0。 步骤2 ：运行Bellman-Ford，计算h(v)： h(A)=0, h(B)=-2, h(C)=-3 步骤3 ：重加权： A→B: -2 + 0 - (-2) = 0 B→C: -1 + (-2) - (-3) = 0 C→A: 4 + (-3) - 0 = 1 C→B: 3 + (-3) - (-2) = 2 步骤4 ：对每个顶点运行Dijkstra（重加权图无负权）： 从A：d'(A,B)=0, d'(A,C)=0, d'(A,A)=0 从B：d'(B,C)=0, d'(B,A)=1, d'(B,B)=0 从C：d'(C,A)=1, d'(C,B)=2, d'(C,C)=0 步骤5 ：恢复原始距离： d(A,B) = 0 - 0 + (-2) = -2 d(A,C) = 0 - 0 + (-3) = -3 d(B,A) = 1 - (-2) + 0 = 3 等等... 7. 关键要点 适用条件 ：无负权环的有向加权图。 核心技巧 ：通过重加权消除负权边，使Dijkstra可用。 优势 ：在稀疏图中，比直接V次Bellman-Ford或Floyd-Warshall更高效。 空间复杂度 ：O(V²)存储所有顶点对距离。 变体应用 ：可用于需要多次计算最短路径的场景，如网络路由协议。 8. 常见面试问题 为什么Johnson算法中重加权后的边权非负？ 如果图中有负权环，Johnson算法如何处理？ 比较Johnson算法与Floyd-Warshall算法的适用场景。 如何证明重加权不改变最短路径？ 为什么选择添加虚拟源点而不是其他方法？