A deep dive into Bellman Ford’s algorithm
What is Bellman Ford’s Algorithm?
It is an algorithm that helps us to compute the shortest path from a vertex to all other vertexes in a weighted graph. The following algorithm was first proposed by Alfonso Shimbel in 1955 but was named after Richard Bellman and Lester Ford Jr. in 1958 and 1956. It is an upgraded version of Dijkstra’s Algorithm and a more flexible and adaptive algorithm as it is capable of handling the edges with negative weight.
Can there be edges with negative weights in real life?
The answer is yes, there are many possibilities where you can find edges having negative weights in real life. For example, consider there are two chemicals, A and B. There are different ways to reach from chemical A to chemical B, involving sub-reactions like absorption and heat dissipation. So now, to find the reactions where minimum energy is required, then we will need to be able to factor in the heat absorption as negative weights and heat dissipation as positive weights.
What are the limitations/disadvantages of Dijkstra’s algorithm?
When we use the algorithm for calculating the shortest path the assumption we make is that all the edges have positive weight, but from the above example we did come to know that in many cases there are negative weights too. Therefore, If we apply this algorithm where we have negative weights, the algorithm would fail to calculate the shortest paths correctly. The reason is that Path(source, destination) might be negative which will make it possible to reach the source from the destination at a lower cost.
How Bellman Ford’s algorithm works?
Bellman Ford’s algorithm operates by calculating the path length from the starting vertex to all other vertices. It then relaxes those estimates iteratively by identifying new routes that are shorter than the previously overestimated paths. This is the base idea of doing it. For getting a clear image of it let’s understand it with an example.
Step 1: Start with the weighted graph.
Step 2: Choose a starting vertex and assign infinity path values to all other vertices.
Step 3: Visit each edge and relax the path distances if they are inaccurate.
Step 4: We need to do this V times because in the worst case, a vertex's path length might need to be readjusted V times.
Step 5: Notice how the vertex at the top right corner had its path length adjusted.
Step 6: After all the vertices have their path lengths, we check if a negative cycle is present.
Algorithm and Pseudocode
In the previous section, we saw how the algorithm works with the help of an example. Now we will be focusing on the real criteria and conditions which are used by the algorithm to solve the problem.
The following steps are:
- The distances from the source to all vertices are set to infinity in this process, while the distance to the source itself is set to 0. An array distance[] is created of size | V | with all the values as infinity except the source vertex.
- The shortest distances are calculated in this step. Follow the steps below |V|-1 times, where |V| is the number of vertices in the graph. Do the following for each u-v edge. If distance[v] > distance[u] + edge uv weight, then distance[v] should be updated to distance[v] = distance[u] + weight if edge uv.
- This phase determines if the graph has a negative weight cycle. For each u-v edge, do the following, “Graph contains negative weight cycle” if distance[v] > distance[u] + edge weight uv.
Step 2 ensures the shortest lengths if the graph does not have a negative weight cycle, which is the principle behind step 3. There is a negative weight loop if we iterate over all edges one more time to get a shorter path for every vertex.
The pseudo-code for the algorithm is:
function bellmanFord(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
distance[S] <- 0
for the number of vertex |v|-1
for each edge (U,V) in G
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
for each edge (U,V) in G
If distance[U] + edge_weight(U, V) < distance[V}
Error: Negative Cycle Exists
return distance[], previous[]Implementation
The Bellman Ford’s algorithm implementation in c++ and python.
C++ :
#include <bits/stdc++.h>struct Edge {
int src, dest, weight;
};struct Graph {
int V, E;
struct Edge* edge;
};struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}void printArr(int dist[], int n){printf("Vertex Distance from Source\n");for (int i = 0; i < n; ++i)printf("%d \t\t %d\n", i, dist[i]);}void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V]; for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0; for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
} for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return; // If negative cycle is detected, simply return
}
} printArr(dist, V);
return;
}
int main()
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1; graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4; graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3; graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2; graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2; graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5; graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1; graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3; BellmanFord(graph, 0);
return 0;
}
Python :
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []def addEdge(self, u, v, w):
self.graph.append([u, v, w])def printArr(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))def BellmanFord(self, src):
dist = [float("Inf")] * self.V
dist[src] = 0 for _ in range(self.V - 1):
for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
dist[v] = dist[u] + w for u, v, w in self.graph:
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
print("Graph contains negative weight cycle")
return self.printArr(dist)
g = Graph(5)
g.addEdge(0, 1, -1)
g.addEdge(0, 2, 4)
g.addEdge(1, 2, 3)
g.addEdge(1, 3, 2)
g.addEdge(1, 4, 2)
g.addEdge(3, 2, 5)
g.addEdge(3, 1, 1)
g.addEdge(4, 3, -3)g.BellmanFord(0)
Time and space complexity analysis:
Though Bellman Ford algorithm is slower than Dijkstra’s Algorithm as it covers the negative weights which is one of the major drawback of Dijkstra’s algorithm, we prefer Bellman Ford’s algorithm more.
Time Complexity:
The total time of the Bellman-Ford algorithm is the sum of initialization time, for loop time, and Relax function time.
- For the best case, the time complexity is O(E).
- For the average case, the time complexity is O(VE).
- For the worst case, the time complexity is O(VE).
where V and E are vertices and edges.
Space Complexity:
The space complexity for Bellman Ford’s algorithm is O(V).
Conclusion
In this article, we took a deep dive into Bellman Ford’s algorithm getting to know about the working and the idea behind the algorithm. We also covered the need of the algorithm and how it overcomes the existing algorithm and studied the importance and existence of negative weight edges.