BELLMAN FORD ALGORITHM

Bellman-Ford algorithm solves the single source shortest path problem in which age, weights can be negative. It finds the shortest path length from a source s B to all v V or determines that a negative weight exists given a weighted directed graph. G=B, E with a source s and a weight w. This algorithm returns a Boolean value indicating whether or not there is a negative weight cycle that is reachable from the source. If there is a negative weight cycle the algorithm indicates that no solution exists. Otherwise, algorithm returns the shortest path and their weight.

BELLMAN _FORD (G,w,s)

  1. INITIALIZE-SINGLE-SOURCE (G,s)
  2. For i←1 to |v[G]|-1
  3. Do for each edge (u,v)  E(G)
  4. do relax(u,v,w)
  5. for each edge(u,v)  E(G)
  6. do if d[v]>d[u]+w(u,v)
  7. then return FALSE
  8. return TRUE

EXAMPLE-1

Image source: Google

EXAMPLE-II

 

Source: Introduction to algorithm by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Contributor's Info

Created:
0Comment