Data Structures and Algorithms: Weighted Graph Processing — Bellman-Ford Algorithm

The Bellman-Ford algorithm is a well-known algorithm used for solving — ‘single source shortest path’ problem. The same problem can be solved using Dijkstra’s algorithm. Before jumping into the algorithm, let’s first have a look at the problem at hand — ‘Single source shortest path’, and how the Bellman-Ford algorithm’s approach is different from Dijkstra's algorithm.

Single-Source Shortest Path Problem

The Bellman-Ford algorithm

The problem is that we have to find the shortest path from the source vertex to all other vertices in the graph. The problem can be solved using both the algorithms — Dijkstra's algorithm and the Bellman-Ford algorithm. So, why do we prefer the Bellman-Ford algorithm to Dijkstra's algorithm? To make a long story short, Dijkstra’s algorithm doesn’t handle a graph with negative weights very well so you may find an answer which is not the optimal solution to the problem.

But that’s where the Bellman-Ford algorithm comes into the picture which can handle negatively weighted edges in the graph unless the graph consists of negative weighted edge cycles.

The approach is also different in both the algorithms, where Dijkstra’s algorithm is a greedy algorithm, whereas the Bellman-Ford algorithm is a dynamic programming-based approach. Both approaches are commonly known for solving optimization problems — where you’re poised to find the optimal solution(either minimum or maximum) to the problem.

Note

If you’re intrigued to learn more about Dijkstra's algorithm, you can refer to my blog on Dijkstra’s algorithm.

Data Structures and Algorithms: Weighted Graph Processing — Part 1: Dijkstra

Note on Edge Relaxation

Edge relaxation is an important concept in algorithms regarding ‘shortest paths calculation’ like Dijkstra’s or Bellman-Ford algorithm. To make it concise, edge relaxation is nothing but:

if(d[u] + c(u,v) < d[v])
d[v] = d[u] + c(u,v)

where, c(u,v) represents the cost/weight along the edge from the vertex u to v. d[x] is the current least-cost/distance to vertex x. Here is an example:

a simple weighted graph: before and after relaxation

Algorithm

1. Choose a starting vertex and assign the distance from the source vertex to all other vertices as infinity.
2. Now, traverse through every edge and relax them while doing so.
3. Now, repeat the process for V-1 times. (where V — is the number of vertices)
4. Run the process one more time, if the edges are being relaxed even after V-1 times then you could conclude that there is a negative cycle in the graph. (more on that later)
5. Else, there’s it you have found the shortest distance from the source vertex to all other vertices after relaxing all the edges for V-1 times.

Pseudo Code

Code

Okay now let’s implement the code for the algorithm by taking the below-weighted graph as an example.

A weighted graph with a negative cycle

If you have observed keenly the graph has a negative cycle: 4 → 3 → 2. In this particular case, the Bellman-Ford algorithm doesn’t work but the code does detect for negative weighted edge cycle and terminates the program if one is found. (more on that later)

The Drawback of Bellman-Ford Algorithm

Unlike Dijkstra’s algorithm, this algorithm can work on graphs containing negative weighted edges. However, if the graph contains a negative cycle, then, clearly the shortest path to some vertice may not exist. As the edges in the negative weighted edge cycle can be relaxed to perpetuity.

You can refer to the workings below with the same example graph with which we implemented the code:

demonstration on the effect of a negative weighted cycle in the graph on the Bellman-Ford algorithm

Output for the above graph with a negative cycle

As you would have noticed, the paths were getting relaxed even after 3 times (as there were 4 vertices in the graph, so V-1 times). It’s because of the negative weighed edge cycle: 4 → 2 → 3.

So, that’s the shortcoming of the Bellman-Ford algorithm, it can’t find an optimal solution when there is a negative weighed edge cycle in the graph.

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post on some other interesting graph algorithms.

Always grateful, never complacent!

References

1. https://www.youtube.com/watch?v=FtN3BYH2Zes&t=928s
2. https://www.programiz.com/dsa/bellman-ford-algorithm
3. https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
4. https://cp-algorithms.com/graph/bellman_ford.html

My Github Repository

1. https://github.com/Sethuram52001/DSA