The Bellman-Ford Algorithm
The Bellman-Ford Algorithm
INITIALIZE-SINGLE-SOURCE(G,s)
for i<-1 to |V[G]|-1 do
for each edge (u,v) of E[G] do
RELAX(u,v,w)
end for
end for
for each edge (u,v) in E[G] do
if d[v] > d[u] + w(u,v) then
return FALSE;
end if
end for
return TRUE