图论算法：Johnsons算法

问题是在给定的加权有向图中找到每对顶点之间的最短路径, 并且权重可能为负。使用Johnsons算法, 我们可以找到所有对在O（V2 log？V + VE）时间中的最短路径。Johnsons算法同时使用Dijkstra算法和Bellman-Ford算法。

Johnsons算法使用“重新加权”技术。如果图中G =（V, E）的所有边缘权重w为非负值, 则可以通过从每个顶点运行一次Dijkstra算法来找到所有顶点对之间的最短路径。如果G具有负负权重边缘, 我们将计算一组新的非负负权重, 从而使我们可以使用相同的方法。新的边缘权重集w必须满足两个基本属性：

1. 对于所有顶点对u, v∈V, 使用权重函数w从u到v的最短路径也是使用权重函数w从u到v的最短路径。
2. 对于所有边缘（u, v）, 新权重w（u, v）为非负数。

给定一个加权有向图G =（V, E）, 权重函数为w：E→R, 而h：v→R为将顶点映射为实数的任何函数。

对于每个边（u, v）∈E定义

其中h（u）= u的标签h（v）= v的标签

JOHNSON (G)
 1. Compute G' where V [G'] = V[G] ∪ {S} and
E [G'] = E [G] ∪ {(s, v): v ∈ V [G] }

 2. If BELLMAN-FORD (G', w, s) = FALSE
    then "input graph contains a negative weight cycle"
  else
    for each vertex v ∈ V [G']
     do h (v) ← δ(s, v)
  Computed by Bellman-Ford algorithm
 for each edge (u, v) ∈ E[G']
   do w (u, v) ← w (u, v) + h (u) - h (v)
 for each edge u ∈ V [G]
 do run DIJKSTRA (G, w, u) to compute
    δ (u, v) for all v ∈ V [G]
  for each vertex v ∈ V [G]
 do duv← δ (u, v) + h (v) - h (u)
Return D.

例：

步骤1：将任何源顶点的’放在图形外, 并使’s’到每个顶点的距离’0’。

步骤2：应用Bellman-Ford算法并计算每个顶点的最小权重。

步骤3：w（a, b）= w（a, b）+ h（a）-h（b）= -3 +（-1）-（-4）= 0

w（b, a）= w（b, a）+ h（b）-h（a）= 5 +（-4）-（-1）= 2 w（b, c）= w（b, c） + h（b）-h（c）w（b, c）= 3 +（-4）-（-1）= 0 w（c, a）= w（c, a）+ h（c）-h （a）w（c, a）= 1 +（-1）-（-1）= 1 w（d, c）= w（d, c）+ h（d）-h（c）w（d, c）= 4 + 0-（-1）= 5 w（d, a）= w（d, a）+ h（d）-h（a）w（d, a）= -1 + 0-（- 1）= 0 w（a, d）= w（a, d）+ h（a）-h（d）w（a, d）= 2 +（-1）-0 = 1

步骤4：现在所有边缘权重都是正的, 现在我们可以在每个顶点上应用Dijkstra算法, 并使矩阵与图中的每个顶点相对应

情况1：“ a”作为源顶点

情况2：“ b”作为源顶点

情况3：“ c”作为源顶点

案例4：将’d’作为源顶点

第五步：

duv←δ（u, v）+ h（v）-h（u）d（a, a）= 0 +（-1）-（-1）= 0 d（a, b）= 0 +（-4 ）-（-1）= -3 d（a, c）= 0 +（-1）-（-1）= 0 d（a, d）= 1 +（0）-（-1）= 2 d（ b, a）= 1 +（-1）-（-4）= 4 d（b, b）= 0 +（-4）-（-4）= 0 d（c, a）= 1 +（-1 ）-（-1）= 1 d（c, b）= 1 +（-4）-（-1）= -2 d（c, c）= 0 d（c, d）= 2 +（0）- （-1）= 3 d（d, a）= 0 +（-1）-（0）= -1 d（d, b）= 0 +（-4）-（0）= -4 d（d, c）= 0 +（-1）-（0）= -1 d（d, d）= 0