algorithm - 约翰逊算法图说明

Question

谁能解释下图的约翰逊算法？我对算法的工作原理感到非常困惑。我知道它是Bellman Ford和的组合Dijkstra's。

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

这是图表。

关于距离的注意事项：从 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的最短路径。这覆盖它吗？