Similar to Dijkstra, Bellman-ford is an algorithm be used to find the shortest path (S.P.) from a source vertex to a particular vertex in a graph. Both algorithms (Dijkstra and Bellman-ford) under go the notion of edge relaxation to find the shortest path.
However unlike Dijkstra, Bellman-ford can handle -ve weight edges and can detect -ve cycles in a graph. The detection of -ve cycles is important because -ve weight edges can lead to -ve cycles which cause undetermined paths.
To understand the motivation of Bellman-ford we should explore the problems encountered when using a generic S.P algorithm to find the S.P. in a given graph. Two such problems:
- Some graphs can cause exponential running time. (link)
- Graphs with -ve cycles are undetermined (infinite loop).
In the example above, a generic S.P. algorithm that doesn’t have -ve cycles will not terminate since relaxation of edges in a cycle causes a infinite loop. Bellman-ford solves problem by terminating the algorithm after V.length -1 iteration and checking for -ve cycles, see below…
Bellman-ford algorithm calculates the shortest distance from source to all vertices in a graph. If a -ve cycle is reported in the check that is run after V.length - 1 passes, the S.P. is not calculated and the algorithm aborts after having detected a -ve cycle.
Below shows how Bellman-ford calculates the S.P. for the graph below:
- Initialize all vertex to infinity.
- Iterate through all Vertices, [V.length - 1]
- For each vertex, relax all the edge from the vertex.
- After all vertices are visited once, check if edge can be relax further for all edges.
- if yes, negative cycle exists if not, no negative cycle.
- if no, do nothing and return the S.P.
// Iterate through all vertices
Bellman-ford works because the S.P. with minimum edges are made up of the shortest sub-path. For example a graph of vertices V0:Vk with no -ve edge cycles, the S.P to a vertex is found by each pass of relaxation. Successive iterations of relaxation until vertex Vk will also be the S.P.:
- Initially, V0, starting vertex is d[V0] = 0.
- After 1st pass through all Edges, d[V1] = δ(S, V1), S.P. from d[V0] to d[V1].
- After 2nd through all Edges, d[v2] = δ(S, V2), S.P. from d[V1] to d[V2].
- After k passes, = d[v] = δ(s, Vk), S.P. is found by sum of δ(S, V1..Vk) (proven by sub-optimal structure lemma)
If a graph has a -ve cycle, the shortest path will not be found after V.length - 1 rounds of relaxation, since further relaxation is possible i.e.: d[v] > d[u] + w(u, v) remains true after having relaxed all edges for all vertices. After V.length - 1 passes, if there is an edge to be relaxed, it means the S.P. is not a simple path and the S.P. has vertices that are repeated (some sort of cycle).
Bellman-ford cannot be used to the longest path of a graph. The diagram shown below shows that the longest path is undetermined because of a cycle that causes a path to be undetermined.
When using the same graph and negating the weights between vertexes and running Bellman-ford for the shortest path, Bellman-ford will not find any path (shortest or longest path) since Bellman-ford aborts after V.length - 1 and detects the -ve cycle. (Bellman-ford can handle -ve weights but not cycles).
Bellman-ford has limited performance with a polynomial running time complexity :
Since V.E dominates, asymptotically the running time is . In the worse case, the total number of edges of a graph can be
V^2, so worse case running time is , cubic time.