图论算法: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定义

Johnsons算法

其中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算法并计算每个顶点的最小权重。

Johnsons算法

步骤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”作为源顶点

Johnsons算法
Johnsons算法

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

Johnsons算法
Johnsons算法

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

Johnsons算法
Johnsons算法

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

Johnsons算法
Johnsons算法
Johnsons算法

第五步:

Johnsons算法

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

Johnsons算法
微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?