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)

- INITIALIZE-SINGLE-SOURCE (G,
s)- for each vertex
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[u] +
w(u,v) < d[v]then- return FALSE
- return TRUE

- 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.