图论算法（Johnsons算法） _图论算法

问题是在给定的加权有向图中找到每对顶点之间的最短路径, 并且权重可能为负。使用Johnsons算法, 我们可以找到所有对在O（V2 log？V + VE）时间中的最短路径。Johnsons算法同时使用Dijkstra算法和Bellman-Ford算法。
Johnsons算法使用“重新加权”技术。如果图中G =（V, E）的所有边缘权重w为非负值, 则可以通过从每个顶点运行一次Dijkstra算法来找到所有顶点对之间的最短路径。如果G具有负负权重边缘, 我们将计算一组新的非负负权重, 从而使我们可以使用相同的方法。新的边缘权重集w必须满足两个基本属性：

对于所有顶点对u, v∈V, 使用权重函数w从u到v的最短路径也是使用权重函数w从u到v的最短路径。
对于所有边缘（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.

【图论算法（Johnsons算法）】例：

文章图片
步骤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