Shortest Paths
Single source shortest paths
Bellman-Ford algorithm solves the single-source shortest paths in the
general case in which edge weights may be negative.
Bellman-Ford ( G, w, s )
Initialise-single-source(G,
s)
for i = 1 to | V[G]| - 1
do for each edge (u, v) in
E[G]
do relax(u, v,
w)
for each edge (u, v) in E[G]
do if d[v] > d[u] +
w(u, v)
then return
FALSE
return TRUE
Initialise-single-source(G , s)
for each vertex v in V[G]
do d[v] = infinity
pi[v] = NIL
d[s] = 0
relax(u, v, w)
if d[v] > d[u] + w(u, v)
then d[v] = d[u] + w(u, v)
pi[v] = u