我们得到以下算法:
输入:二部图G=(L,R,E)
、权重函数w:E->Z
和源顶点s in L
算法:
1) 定义 E1={(u,v) in E | u in L,v in R}
和 E2=E\E1
2) 为 L 和 R 中的所有顶点初始化 d(s)=0
和 d(v)=inf
(s 除外)
3) 执行 floor((|L|+|R|)/2)
次:
A.通过所有边 (u,v) in E1
:
if d(v) > d(u) + w(u,v)
then d(v) = d(u) + w(u,v)
B.通过所有边 (u,v) in E2
:
if d(v) > d(u) + w(u,v)
4) 为每个顶点返回d(v)
这个算法给出了从 s
到所有其他顶点的最短路径,我们被要求证明它的正确性。现在,据我所知,正确性证明应该与 Bellman-Ford 的算法完全一样(在路径长度上使用归纳法),但我不知道我应该做哪些更改才能使其工作对于这个算法。
我不确定我是否可以在这里提出这样的问题,但过去 4 天我一直在讨论这个问题,我似乎看不出与 bellman-ford 的正确性证明有什么不同。
有什么建议吗?
谢谢:)