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
Thus, the Bellman-Ford algorithm runs in O(E) time.