Bellman–Ford algorithm: Difference between revisions

Revision as of 05:22, 19 June 2003

Revision as of 21:31, 13 November 2003

Line 6:

BF(G,w,s) // G = Graph, w = weight, s=source

Determine Single Source(G,s);

set Distance(s) = 0; Predecessor(s) = nil;

for i <- 1 to |V(G)| - 1 //|V(G)| Number of Vertices in the graph

for each vertex v doin forG eachother edgethan ins, G

set Distance(v) = infinity, Predecessor(v) = nil;

do Relax edge

for i <- 1 to |V(G)| - 1 do //|V(G)| Number of Verticesvertices in the graph

for each edge in G

for each edge (u,v) in G do

do if Cost of Vertice r > Cost to Vertice r from Vertice u

if Distance(v) > Distance(u) + w(u,v) then

return false

set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u;

return true

for each edge (u,r) in G do

if Distance(r) > Distance(u) + w(u,r);

return false;

return true;