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

Question

Code below is from 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

Following is from Algorithms, 4th edition.

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

It seems that the only difference is the number of passes.

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

and

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

Which one is right?

Answer 1

EDIT: the question was actually about the number of passes on the outer loop: N-1 or N. Bellman's paper linked below states "The functional equation technique of dynamic programming, combined with approximation in policy space, yields an iterative algorithm which converges after at most(N — 1) iterations." The justification is given in CLRS in Lemma 24.2 and its proof.

ORIGINAL ANSWER:

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

and:

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

are equivalent for the purpose of this algorithm: they both iterate once over every edge of the graph. The second version just iterates over all the vertices first, and for each vertex, iterates over its incident edges.

As for lines 5-7 of CLRS they check that there is no negative-weight cycle, but that is apparently ignored in the extract you posted from Algorithms, 4th edition. Checking Bellman's original paper I don't see this final check, so it may be an addition of CLRS or other .