哪个版本的 Bellman-Ford 算法是正确的，CLRS 还是算法？

Question

以下代码来自Introduction to Algorithms, 3rd edition.

BELLMAN-FORD(G,w,s)
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 for i = 1 to |G.V|-1
3   for each edge (u,v) ∈ G.E
4       RELAX(u,v,w)
5 for each edge (u,v) ∈ G.E
6    if v.d > u.d + w(u,v)
7       return FALSE
8 return TRUE

以下内容来自算法，第 4 版。

for (int pass = 0; pass < G.V(); pass++)
   for (int v = 0; v < G.V(); v++)
      for (DirectedEdge e : G.adj(v))
          relax(e);

似乎唯一的区别是传球次数。

for i = 1 to |G.V|-1

和

for (int pass = 0; pass < G.V(); pass++)

哪一个是正确的？

Answer 1

编辑：问题实际上是关于外循环的传递次数：N-1 或 N。下面链接的 Bellman 论文指出“动态规划的函数方程技术，结合近似在策略 space 中，产生一个迭代算法，该算法在最多 (N - 1) 次迭代后收敛。” CLRS 在 Lemma 24.2 and its proof.

中给出了理由

原始答案：

for each edge (u,v) ∈ G.E

和：

for (int v = 0; v < G.V(); v++)
  for (DirectedEdge e : G.adj(v))

就此算法而言，它们是等效的：它们都在图的每条边上迭代一次。第二个版本只是首先遍历所有顶点，然后对于每个顶点，遍历其入射边。

至于 CLRS 的第 5-7 行，他们检查没有负权重循环，但在您从 算法，第 4 版 发布的摘录中显然忽略了这一点。正在检查 Bellman's original paper 我没有看到最后的检查，因此可能是添加了 CLRS 或其他 .

Answer 2

到图中任意顶点的最短路径最多有|V|-1条边，最多到达|V|-1 verices other than source.

Nth运行遍历所有边后，保证沿任意最短路径到达的Nth顶点有分配了正确的成本，因此该算法只需要 |V|-1 遍来计算所有最短路径。

哪个版本的 Bellman-Ford 算法是正确的，CLRS 还是算法？

Which version of Bellman-Ford algorithm is right, CLRS or Algorithms?

algorithm

graph

bellman-ford