Bellman-Ford Algorithm

 

Bellman-Ford algorithm solves the single-source shortest-path problem in the general case in which edges of a given digraph can have negative weight as long as G contains no negative cycles.

This algorithm, like Dijkstra's algorithm uses the notion of edge relaxation but does not use with greedy method. Again, it uses d[u] as an upper bound on the distance d[u, v] from u to v.

The algorithm progressively decreases an estimate d[v] on the weight of the shortest path from the source vertex s to each vertex v in V until it achieve the actual shortest-path. The algorithm returns Boolean TRUE if the given digraph contains no negative cycles that are reachable from source vertex s otherwise it returns Boolean FALSE.

 

BELLMAN-FORD (G, w, s)

  1. INITIALIZE-SINGLE-SOURCE (G, s)
  2. for each vertex i = 1 to V[G] - 1 do
  3.     for each edge (u, v) in E[G] do
  4.         RELAX (u, v, w)
  5. For each edge (u, v) in E[G] do
  6.     if d[u] + w(u, v) < d[v] then
  7.         return FALSE
  8. return TRUE

 

Analysis

Thus, the Bellman-Ford algorithm runs in O(E) time.