从 CLRS 理解 BELLMAN-FORD 算法

Understanding BELLMAN-FORD algorithm from CLRS

考虑这个简单的图表:

S -> A -> B -> C

在 CLRS 中,作者实现了一个指向 |V|-1 的循环。 但是根据 path-relaxation property 一个简单的路径 P 可以是 < s,a,b,c >。

使用 path-relaxation property 我们将按以下顺序松弛 P 的边缘

(S,A),(A,B),(B,C)

因此,我们将一次性完成 |V| - 1 次迭代。 |V| -1 passes的使用我可以理解,如果path-relaxation property不指定我们放宽路径,从'the source'开始。

|V|有什么意义- 这里有 1 次迭代?我哪里错了,有解释。

因为任何两个节点之间的任何最短路径不能包含大于 |V| 个节点或 |V|-1 个边。通过将边缘松弛 |V|-1 次,我们确信我们已经获得了两个节点之间的最佳距离(如果存在最佳路径的话)。