Lecture
The Bellman-Ford algorithm solves the single-source shortest path problem in the general case, where the weight of each edge may be negative. For a given weighted directed graph G = (V, E) with source s and weight function w : E —» R, the Bellman-Ford algorithm returns a Boolean value indicating whether the graph contains a negative-weight cycle reachable from the source. If such a cycle exists, the algorithm indicates that no solution exists. If no such cycles exist, the algorithm produces the shortest paths and their weights.
This algorithm uses relaxation, whereby the value d[v], an estimate of the weight of the shortest path from source s to each vertex v ∈ V, is decreased until it equals the actual weight of the shortest path from s to v. The algorithm returns TRUE if and only if the graph does not contain any negative-weight cycles reachable from the source.
Bellman_Ford(G, w, s) 1 Initialize_Single_Source(G, s) 2 for i «- l to |V[G]|-1 3 do for each edge (u, v) ∈ E[G] 4 do RELAX(u,v,w) 5 for each edge (u, v) ∈ E[G] 6 do if d[v] > d[u] + w(u, v) 7 then return FALSE 8 return TRUE
After all values of d and prev are initialized in line 1, the algorithm makes |V| — 1 passes over the edges of the graph. Each pass corresponds to one iteration of the for loop in lines 2-4 and consists of relaxing each edge of the graph once. After |V| — 1 passes, lines 5-8 check for the presence of a negative-weight cycle and return the corresponding Boolean value.
The Bellman-Ford algorithm completes its work in time O(V*E), since the initialization in line 1 takes O(V) time, each of the |V| — 1 passes over the edges in lines 2-4 requires O(E) time, and executing the for loop in lines 5-7 takes — O(E) time. .
Comments