Algorithm - Bellman-ford, shortest path

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.

Why Bellman-ford ?

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:

  1. Some graphs can cause exponential running time. (link)
  2. Graphs with -ve cycles are undetermined (infinite loop).

Image shows a -ve weight cycle causing undetermined path (infinite loop), d[u] is the distance from u vertex. Orange box showing -ve cycle.

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

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:

Bellman-ford showing each iteration of relaxation finds the shortest path. The graph has a -ve weights but no -ve cycles.

  1. Initialize all vertex to infinity.
  2. Iterate through all Vertices, [V.length - 1]
  3. For each vertex, relax all the edge from the vertex.
  4. 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.
1
2
3
4
// Iterate through all vertices
// Relax all edges
// Check all edges to see if further relaxation is possible
// abort if -ve cycle.

Bellman-ford code example for resolving graph with -ve weights

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

Bellman-ford showing each iteration of relaxation finds the shortest path.

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

Longest Simple Path & Shortest Simple Path

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.

Using Bellman-ford for finding longest path will not work (left), Bellman-ford can find the shortest path of on left.

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

Time complexity

Bellman-ford has limited performance with a polynomial running time complexity :

θ(VE+E)\theta (VE + E)

Since V.E dominates, asymptotically the running time is θ(VE)\theta(VE) . In the worse case, the total number of edges of a graph can be V^2, so worse case running time is θ(V3)\theta(V^3) , cubic time.