Back	Table of contents

Bellman-Ford's Algorithm

    The Bellman Ford algorithm solves the single-source shortest-paths problem in the more general case in which edge weights can be negative. Given a weighted, directed graph G = (V,E) with source s and weight function w from E to R, the Bellman Ford algorithm returns a boolean value indicating whether or not there is a negative weight cycle reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.

    Like Dijkstra's algorithm, the Bellman Ford algorithm uses the technique of relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v belonging to V until it achieves the actual shortest path weight. The algorithm returns TRUE if and only if the graph contains no negative weight cycles that are reachable from the source.

BELLMAN - FORD (G, w, s)

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

    After performing the ususal initialisation, the algorithm makes |V| -1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. After making |V|-1 passes, lines 5-8 check for a negative weight cycle and return the appropriate boolean value.
    The Bellman Ford algorithm runs in time O(V E), since the initialisation in line 1 takes theta(V) time, each of the |V|-1 passes over the edges in lines 2-4 takes O(E) time, and the for loop of lines 5-7 takes O(E) time.