Bellman-Ford Algorithm with Example

Bellman Ford is an algorithm used to compute single source shortest path. This means that starting from a single vertex, we compute best distance to all other vertices in a weighted graph. This is done by relaxing all the edges in the graph for n-1 times, where n is the number of vertices in the graph. Dijkstra's algorithm also achieves the same goal, but Bellman ford removes the shortcomings present in the Dijkstra's.

When and Why to use Bellman Ford?

As stated above, Dijkstra's also achieves the same goal, but if any negative weight cycle is present, it doesn't work as required. A negative weight cycle is a loop in the graph with some negative weight attatched to an edge. sum of weights in this loop is negative. A node's value decrease once we go around this loop. A graph having negative weight cycle cannot be solved. Consider this graph, it has a negative weight cycle in it.

After every BCD loop, the value of node B will change. The problem with Dijkstra's algorithm is that it doesn't detects whether a graph is having this negative weight cycle or not. Bellman Ford on the other hand detects this cycle and tells us that this problem cannot be solved.

Edge Relaxation

If we have an edge between vertices u and v (from u to v), dist[u] represents the distance of the node u, and weight[uv] represents the weight on the edge, then mathematically, edge relaxation can be written as,
If dist[u] + weight < dist[v], then
dist[v] = dist[u] + weight
Consider this graph, we're relaxing the edge.

Working through the Algorithm

Consider this weighted graph,

Initially we've set the distance of source as 0, and all other vertices are at +Infinity distance from the source. We will now relax all the edges for n-1 times. Here n = 7, so 6 times.
Look at the edge AB,
dist[A] = 0, weight = 6, and dist[B] = +Infinity
Since the relaxation condition is true, we'll reset the distance of the node B.

Similarly, lets relax all the edges.

We can see that in the first iteration itself, we relaxed many edges. Now we have to continue doing this for 5 more times.
Relaxation 2nd time

Relaxation 3rd time

Relaxation 4th time

We notice that edges have stopped changing on the 4th iteration itself. This means that all the edges have now relaxed. A graph without any negative weight cycle will relax in n-1 iterations.

Checking the presence of negative weight cycle

If after n-1 iterations, on the nth iteration any edge is still relaxing, we can say that negative weight cycle is present. Once it's confirmed that there's a negative weight cycle present in the graph, an error message is shown denoting that this problem cannot be solved.

Pseudocode for Bellman Ford:

• Create an array dist[] of size V (number of vertices) which store the distance of that vertex from the source.
• Initialize dist[0] to 0 and rest values to +Inf.
• Repeat this process for V-1 times:
  1. For each edge u-v in the graph,
     If dist[u] + weight < dist[v],
     dist[v] = dist[u] + weight
• For any edge in the graph, if dist[u] + weight < dist[v], Negative weight cycle is present