Bellman–Ford Algorithm

What is Bellman-Ford Algorithm?

The Bellman-Ford algorithm computes the shortest path from a source vertex to all others in a graph, accommodating both weighted and unweighted edges. While it's generally slower than Dijkstra’s method, Bellman-Ford excels in graphs with negative edge weights and detects negative cycles, a crucial feature. This capability prevents infinite loops where path costs decrease infinitely by traversing negative cycles. Utilizing dynamic programming, Bellman-Ford employs a bottom-up approach, iteratively refining distance estimates via the "Principle of Relaxation." Starting with immediate neighbors, it progressively evaluates longer paths, converging to the optimal solution. However, if negative weight cycles exist, they can distort path distances, necessitating caution during analysis. Thus, Bellman-Ford offers a robust, albeit slower, alternative for diverse graph scenarios.

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