Bellman–Ford Algorithm

Introduction

Suppose that we are going for a picnic, there may be some path leading to the picnic spot where we have to pay taxes and some paths which have houses of our relatives/friends who will give us gifts if we pass by their home. To find the optimal path (path with the least cost) from home to picnic spot we need Bellman Ford Algorithm.

Bellman ford algorithm is used to calculate the shortest paths from a single source vertex to all vertices in the graph.

This algorithm also works on graphs with a negative edge weight cycle (It is a cycle of edges with weights that sums to a negative number), unlike Dijkstra which gives wrong answers for the shortest path between two vertices.

Bellman Ford algorithm is easier to implement when compared to dijkstra algorithm and optimal for distributed systems. (but on the other hand, it has a high time complexity i.e. $O(VE)$ where V and E are numbers of vertices and edges respectively.

Example of Bellman Ford Algorithm

Suppose that we have a graph consisting of 5 vertices having edges between them as shown in the picture below. Now, we want to find shortest distance to each vertex v_i 0<i<6 starting from the vertex 1.

After performing bellman ford algorithm on the above graph the output array would look like - Shortest_Distance = [0, 3, 5, 2, 5]

Where each index 'í' of array denotes the shortest distance of the i^th vertex from 1^st vertex, 1<=i<=5.

How Bellman Ford Algorithm Works?

The algorithm works by iteratively relaxing the edges of the graph to find the shortest path.

Here are the step-by-step workings of the Bellman-Ford algorithm:

Step 1: Initialize distances and predecessors

The algorithm starts by initializing the distance of the source node to 0 and the distances of all other nodes in the graph to infinity.

Step 2: Relax edges

The algorithm then iteratively relaxes the edges of the graph. For each edge u→v with weight w, it checks if the distance to v can be improved by going through u. If the distance can be improved, it updates the distance of v and sets its predecessor to u.

Above step is repeated V-1 times for every edge.

Step 3: Check for negative cycles

After all the edges have been relaxed, the algorithm checks for negative cycles in the graph. A negative cycle is a cycle whose total weight is negative. If there is a negative cycle in the graph, the algorithm reports it and terminates. Step 2 (relax edges) is repeated one more time for all the edges. If there is some edge some which can be further relaxed then we say that there is an negative cycle present in the graph.

Step 4: Shortest paths

If there are no negative cycles in the graph, the algorithm returns the shortest path from the source node to every other node in the graph.

Input:

• A 2D Array/List denoting edges and their respective weights.
• A src vertex.

Output: An array where each index denotes the shortest path length between that vertex and src vertex.

Procedure:

1. In this step, we would declare an array of size V(Number of vertexes) say dis[] and initialize with all of its indexes with a very big Value (preferably INT_MAX) except src which will be initialized with value 0. We are doing this because initially we assume that it takes infinite time to reach any of the vertices from our source vertex and we are initializing dis[src]=0 because we are already on source vertex.

2. In this step, the shortest distance is calculated. For it, we would do the underlying step V-1 times. For every edge u→v make dis[v]=min(dis[u]+ wt of edge u→v, dis[v]) It means whenever we are on any vertex u we will check if we can reach any of its neighbors in less time it is currently possible to visit, we will update the dis[v] to dis[u]+wt of edge u→v.

3. In this step, we will check if there exists a negative edge weight cycle traversing each and every edge u→v and checking if there exists dis[u] + wt of edge u→v < dis[v] then our graph contains a negative edge weight cycle because traversing the edges again and again is beneficial as it is lowering the cost to traverse the graph. --> :::