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

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:

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.

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

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

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 :

$\theta (VE + E)$

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