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

• The initialization in line 1 takes (v) time
• For loop of lines 2-4 takes O(E) time and For-loop of line 5-7 takes O(E) time.

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