Bellman-Ford Algorithm

Bellman Ford Algorithm

You are given a Weighted Graph. You know the source and need to find the shortest path to reach all the other vertices. What do you do to solve this problem? You choose Dijkstra’s Algorithm. But what if there are negative weights included? Dijkstra’s can’t work on negative weights. We now need a new algorithm.

The Bellman-Ford algorithm is an algorithm almost like Dijkstra that’s it finds the shortest path during a graph from one source vertex to all or any other vertices during a weighted graph but works even in cases of negative weights if implemented correctly.

This algorithm is used to compute the shortest path from a single source vertex to all other vertices. Bellman Ford uses a dynamic programming like approach and is capable of detecting negative cycles unlike Breadth First Search and Dijkstra.

A negative weight is just a relative value on top of and edge.

In general, a cycle in a graph refers to a path where the first vertex and the last vertex of that path are the only repeated vertices or the path begins and ends at the same vertex. In simpler words, it can be referred to as a closed path.

We see two cycles here:

• E → F → G → H → I → J → E
• K → L → M → N → O → P → K

In both these cases, the first and the last vertex in the path are same and thus form a cycle.

The algorithm

— Relax each edge in the graph for Y-1 times.

Relaxing an edge (x,y) -

Let’s call d[y] as the length of the current minimum distance path starting from vertex s. The process of relaxing tries to improve the shortest path to y by going through x. We update d[y] only if going through x is shorter than the current estimate d[y]

RELAX(x,y,z):

if ( d[y] > d[x] + w(x,y) )

d[y] = d[x] + w(x,y);

Algorithm for Bellman Ford:

1. Assume all the nodes are not visited and all nodes are at a distance of infinity from the starting node
2. We select the source node, and initialize the distance needed as 0
3. Now, we try to RELAX each edge (Y-1) times

Why do we Relax (Y-1) times?

The algorithm uses the bottom-up approach to calculate the shortest path. The bottom-up approach consists in first looking at the smaller sub-problems, and then solve the larger sub-problems using the solution obtained while solving the smaller sub-problems. It first calculates the shortest path that are the direct neighbors of s, followed by second level neighbors, … up to Y-1 level neighbors.

function bellmanFord(G, S)
	for each vertex V in G
			D[V] <- infinite
			
	D[S] <- 0
	for each vertex V in G				
		for each edge (U,V) in G
		  tempDistance <- D[U] + edge_weight(U,V)
			if tempDistance < D[V]
			   D[V] <- tempDistance
			   	for each edge (U,V) in G
		If D[U] + edge_weight(U, V) < D[V]
			Error: Negative Cycle Exists
                        return	print D[]

Telling the definition first, the Bellman-Ford algorithm works by first overestimating the length of the path from the starting vertex to all other vertices. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated paths. Finally, it checks for negative cycles

In simpler terms, let Y be the number of vertices, X be the number of edges, S be the starting node, and D be an array which tracks the best distance between the source node and rest vertices.

Following the step of overestimation, we set each entry in the array to positive infinity. We assign the highest value possible because the distance is unknown to us. Now we assign D[S]=0. So we have reached the state shown below

for each vertex V in G
			D[V] <- infinite
			previous[V] <- NULL
	distance[S] <- 0

Now, infinite levels are too high for us. So its time to relax. In this step, we aim to find what we have been looking for, the shortest path to each vertex. We start a loop that will run Y times for each edge because in the worst case, a vertex’s path length might need adjustment Y times. In the loop, for each edge, we take the value of the vertex from where the edge is starting (D[X]) and add it to the edge cost. This added value is them compared to the value of the vertex where the edge is ending (D[Y]). If the sum value is found to be less, the end vertex value (D[Y]) becomes equal to the sum.

for each vertex V in G				
		for each edge (U,V) in G
		  tempDistance <- D[U] + edge_weight(U,V)
			if tempDistance < D[V]
			   D[V] <- tempDistance

A simple graphical representation of Bellman Ford:

It was taken from Maxim Kjaer’s blog.

Bellman-Ford vs. Dijkstra

There are two main differences between both algorithms:

1- Fast Vs. Guaranteed: Dijkstra is a greedy algorithm. It might compromise, just the slightest, on the globally optimal solution, in an effort to accomplish the task within the fastest manner. In contrast, Bellman-Ford makes sure that the trail it finds is that the global optimal solution while compromising on the time it finds it. Most solutions tend to lean towards Dijkstra’s algorithm due to the need of faster solutions. However, if the optimal time isn’t the very best priority, Bellman-Ford is one among the higher shortest path algorithms.

2-Negative Edges/Cycles: Dijkstra’s algorithm can’t handle negative edges or cycle. This is where Bellman-Ford shines within this comparison. If you’ve got a use case where time is a particularly high priority, but it contains negative weights, you can’t use Dijkstra due to this specific limitation. Many algorithms can handle negative weights but fail to detect negative cycles. With Bellman-Ford, this could not be a problem if it’s implemented correctly.