algorithm - 约翰逊算法图解

Question

谁能解释下图中的约翰逊算法？我真的很困惑算法是如何工作的。我知道它是 Bellman Ford 和 Dijkstra 的 的组合。

但我无法找到一个很好的图形解释，逐步解释解决方案。

这是图表。

关于距离的注意事项:从 f 到 b 是 -5(不是 5)； g 到 e 是 -3(不是 3)； b 到 d 是 -5(不是 5)

非常感谢。我知道我必须先改变权重，但我不确定如何改变权重。

问题:我想找到从 b 到 c 的最短路径。

Answer 1

正如您已经完成的那样，我们引入了一个新节点，称为 z，与所有其他节点的权重为 0 连接。我们计算出从 z 到彼此路径的最短路径并得到:

h(a) =   0
h(b) =  -5
h(c) =   0
h(d) = -10
h(e) =  -4
h(f) =   0
h(g) =  -1

然后我们重新计算边的权重:

w'(a,d) = w(a,d) + h(a) - h(d) = 11 +    0  - (-10) = 21
w'(b,a) = w(b,a) + h(b) - h(a) =  7 +  (-5) -    0  =  2
w'(b,d) = w(b,d) + h(b) - h(d) = -5 +  (-5) - (-10) =  0
w'(c,a) = w(c,a) + h(c) - h(a) = 17 +    0  -    0  = 17
w'(c,b) = w(c,b) + h(a) - h(b) =  3 +    0  -  (-5) =  8
w'(d,f) = w(d,f) + h(d) - h(f) = 12 + (-10) -    0  =  2
...

然后使用 Dijkstra 找到从 a 到 b 的最短路径。这涵盖了吗？