Bellman Ford Algorithm
Introduction
Let us consider a case where you are given a weighted graph, i.e., a graph whose edges have weights. You are also given the source and destination points, and now you have to find the shortest path from the source to the destination. You can solve this using the Dijkstra algorithm, but what if the graph contains negative weights? The Dijkstra algorithm will fail in this case. An algorithm called the Bellman Ford algorithm would be used to solve this problem.
In this blog, we will cover the Bellman-Ford algorithm in detail, along with the code in Java. Since this algorithm is based on graphs, so you need to know the traversals in the graph (DFS, BFS).
Bellman Ford algorithm
The Bellman-Ford algorithm is similar to the Dijkstra algorithm. These algorithms find the shortest path in a graph from a single source vertex to all the other vertices in a weighted graph.
The Bellman Ford Algorithm is used in coding problems like minimum cost maximum flow from a graph, single-source shortest path between two cities, print if there is a negative weight cycle in a directed graph, the path with the smallest sum of edges with weight>0, etc.
The difference between the Dijkstra and the Bellman-Ford algorithms is that the Bellman Ford algorithm can be used when the edge weight is negative.
The Dijkstra algorithm follows a greedy approach. Once a node is marked as visited, it is not reconsidered even if there is another shortest path. Due to this reason, the Dijkstra algorithm does not work when there is a negative edge weight in the graph.
Problem Statement
A directed weighted graph with N vertices labeled from 0 to N-1 and M edges is given. Each edge connecting two nodes, u, and v, has a weight of w, denoting the distance between them. The task is to find the shortest path length between the source and vertices given in the graph. Suppose there is no path possible, print “There is a negative cycle in the graph”. The graph may also contain negatively weighted edges.
Algorithm
In the Bellman-Ford algorithm, we overestimate the length of the path from the source vertex to all other vertices. Then the edges are relaxed iteratively by finding new paths that are shorter than the previously overestimated paths. This algorithm uses the concept of dynamic programming and calculates the shortest paths in a bottom-up manner.
Let's look at the psuedocode now.
Pseudocode
1. Create an array to store the path length from source to destination.
2. Initialize all distances to maximum value except source.
3. Initialize the distance from source to source as 0.
4. Repeat (N-1) times
For every edge from source to destination
if path[v] > path[u] + weight(uv)
path[v] = path[u] + weight(uv);
Where "u" is the source node, "v" is the destination node, and "weight(uv)" is the edge weight.
5. If there is no path possible, print “There is a negative cycle in the graph”.
Now let us understand the Bellman Ford algorithm with the help of an example.
Dry Run
Consider the directed weighted graph with source vertex 0. Number of vertices and edges in the graph is 5 and 7 respectively.
1. Initially since the source vertex is 0, therefore the dest[0] = 0. Now, first, we will process the node (2,4). Now according to the formula,
if(dist[u] + wt < dist[v])
dist[v] = dist[u] + wt
Here u and v are vertices and wt is the weight of the edge between them. The values are dist[0]=INF, dist[2]=INF, and wt = 2, now since the value of dist[2] is greater is nearly equal to dist[4] + wt (since both are infinity), therefore the value of dist[4] would remain infinity. Like this, we will process all the edges and the final array would look like the one given in the image below:
2. After processing all the edges again in the order given below, the final array would look like the one given in the 7th iteration in the image,
3. Now in this iteration we will get our final values for our distance array after this also one iteration is left but it would yield the same result as this one.
Implementation in Java
Let's see how the Bellman Ford algorithm is implemented in Java.
import java.util.ArrayList;
import java.util.Arrays;
public
class Main{
private
static void bellmanFord(int n, int m, int src, ArrayList<ArrayList<Integer>> edges){
// create an array to store the path length from source to i
int[] path = new int[n];
// fill the array with the max value
Arrays.fill(path, Integer.MAX_VALUE);
// distance of source to source is 0
path[src] = 0;
int f = 1;
// bellman ford algorithm
for (int i = 0; i <= n; i++){
for (int j = 0; j < m; j++){
// u node
int u = edges.get(j).get(0);
// v node
int v = edges.get(j).get(1);
// edge weight
int w = edges.get(j).get(2);
if (i == n && path[u]!= Integer.MAX_VALUE && path[v] > (path[u] + w) ){
System.out.println("There is a negative cycle in the graph");
f = 0;
break;
}
// relaxation
else if (i<n && path[u] != Integer.MAX_VALUE && path[v] > (path[u] + w)){
path[v] = path[u] + w;
}
}
}
// if there is no negative cyle
if (f == 1){
// then print the shortest path of every node from the source node
for (int i = 0; i < n; i++){
System.out.print("The shortest path between " + src + " and " + i + " is: ");
if(path[i]==Integer.MAX_VALUE){
System.out.println("No Path");
}
else{
System.out.println(path[i]);
}
}
}
}
// driver code
public
static void main(String[] args){
int n = 5, m = 7, src = 0;
ArrayList<ArrayList<Integer>> edges = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> edge1 = new ArrayList<Integer>();
edge1.add(2);
edge1.add(4);
edge1.add(3);
ArrayList<Integer> edge2 = new ArrayList<Integer>();
edge2.add(4);
edge2.add(3);
edge2.add(3);
ArrayList<Integer> edge3 = new ArrayList<Integer>();
edge3.add(0);
edge3.add(2);
edge3.add(2);
ArrayList<Integer> edge4 = new ArrayList<Integer>();
edge4.add(3);
edge4.add(1);
edge4.add(-3);
ArrayList<Integer> edge5 = new ArrayList<Integer>();
edge5.add(1);
edge5.add(2);
edge5.add(1);
ArrayList<Integer> edge6 = new ArrayList<Integer>();
edge6.add(2);
edge6.add(3);
edge6.add(4);
ArrayList<Integer> edge7 = new ArrayList<Integer>();
edge7.add(0);
edge7.add(1);
edge7.add(-1);
edges.add(edge1);
edges.add(edge2);
edges.add(edge3);
edges.add(edge4);
edges.add(edge5);
edges.add(edge6);
edges.add(edge7);
bellmanFord(n, m, src, edges);
}
}
Output
The shortest path between 0 and 0 is: 0
The shortest path between 0 and 1 is: -1
The shortest path between 0 and 2 is: 0
The shortest path between 0 and 3 is: 4
The shortest path between 0 and 4 is: 3Complexity Analysis
Time Complexity: Since in the above approach, all the edges are relaxed for (N-1) times. So the time complexity is O(M * (N-1)), which can be simplified to O(M * N).
Space complexity: The space complexity is O(N), as the extra space is required to store the array elements.
Here M is the number of edges and N is the number of vertices.
Implementation in C++
Now, let's see how the Bellman Ford algorithm is implemented in C++.
#include <bits/stdc++.h>
using namespace std;
void bellmanFord(int n, int m, int src, vector<pair<pair<int, int>, int>> adj){
// creating an array to store the path length from source to i
int path[n];
// filling the array with max value
for (int i = 0; i < n; i++)
path[i] = 1e9;
// distance from source to source is 0
path[src] = 0;
bool flag = false;
// bellman ford algorithm
for (int i = 0; i <= n; i++){
for (int j = 0; j < adj.size(); j++){
// u node
int u = adj[j].first.first;
// v node
int v = adj[j].first.second;
// edge weight
int wt = adj[j].second;
if (i == n && path[v] > (path[u] + wt)){
flag = true;
cout << "There is a negative cycle in the graph" << endl;
break;
}
// relaxation
else if (i < n && path[u] != 1e9 && path[v] > (path[u] + wt)){
path[v] = path[u] + wt;
}
}
}
// if there is no negative cyle
if (!flag){
// then print the shortest path of every node from the source node
for (int i = 0; i < n; i++){
cout <<"The shortest path between " << src <<" and " << i <<" is: " ;
if(path[i]==1e9){
cout<<"No Path\n";
}
else{
cout<< path[i] << endl;
}
}
}
}
int main(){
int n = 5, m = 7, src = 0;
// vector to store the nodes u and v and the weight
// of edge connecting them like this {{u,v},wt}
vector<pair<pair<int, int>, int>> adj;
adj.push_back({{2, 4}, 3});
adj.push_back({{4, 3}, 3});
adj.push_back({{0, 2}, 2});
adj.push_back({{3, 1}, -3});
adj.push_back({{1, 2}, 1});
adj.push_back({{2, 3}, 4});
adj.push_back({{0, 1}, -1});
bellmanFord(n, m, src, adj);
}
Output
The shortest path between 0 and 0 is: 0
The shortest path between 0 and 1 is: -1
The shortest path between 0 and 2 is: 0
The shortest path between 0 and 3 is: 4
The shortest path between 0 and 4 is: 3Complexity Analysis
Time Complexity: Since in the above approach, all the edges are relaxed for (N-1) times. So the time complexity is O(M * (N-1)), which can be simplified to O(M * N).
Space complexity: The space complexity is O(N), as the extra space is required to store the array elements.
Here M is the number of edges and N is the number of vertices.
Why (N-1) iterations?
In the Bellman Ford algorithm, there is a chance that the shortest path is obtained before completing (N-1) iterations. However, in the worst case, the shortest path to all the vertices is obtained only at the (N-1)th iteration, which is why we repeat the process of relaxation (N-1) times. Let's see the case where (N-1) iterations are required.
As you can see, the shortest path from source "a" to destination "e" is obtained only in the (N-1)th, i.e., the 4th iteration.
Does it work for negative cycles?
If the total weight of the edges is negative, the weighted graph has a negative cycle. The Bellman Ford algorithm does not work here as there is no shortest path in this case. However, the Bellman Ford algorithm can detect the negative cycle.
Bellman ford relaxes all the edges to find the optimum solution. If there is a negative cycle, the Bellman Ford algorithm will keep ongoing indefinitely. It will always keep finding a more optimized solution, i.e., a more negative value than before. So it becomes necessary to identify the negative cycle.
As you can notice, after every cycle, the shortest path keeps on decreasing. To identify the negative cycle, the edges are relaxed again. If the solution is reduced more, there is a negative cycle.
Frequently Asked Questions
Is the Bellman Ford algorithm faster than the Dijkstra algorithm?
No, the Dijkstra algorithm is faster than the Bellman Ford algorithm. The time complexity of the Dijkstra algorithm is O(M * log N), and the time complexity of the Bellman Ford algorithm is O(M * N).
Where "M" is the number of edges and "N" is the number of vertices.
In the Bellman Ford algorithm, why is the source vertex path set to 0 and the other vertices path to the maximum value?
The source vertex path is set to 0 as the distance between the source to source is 0. The path of other vertices is set to maximum because the distance to each node initially is unknown, so we assign the highest value possible.
How is the Dijkstra algorithm different when compared to the Bellman Ford algorithm?
The difference between the Dijkstra algorithm and Bellman Ford algorithm are:-
The Dijkstra algorithm uses the greedy approach, whereas the Bellman Ford algorithm uses dynamic programming.
In the Dijkstra algorithm, the minimum value of all vertices is found, while in the Bellman-Ford algorithm, edges are considered one by one.
List all the shortest path algorithms.
The shortest path algorithms are Dijkstra Algorithm, Bellman Ford, Floyd Algorithm, Johnson Algorithm, and Topological Sort.
Which is a more space-efficient adjacency list or adjacency matrix?
Well, in the case of the adjacency matrix worst-case space complexity is O(V*V) where V is the no vertices in the graph, and the adjacency list takes O(V) space in the worst case. So we can say that the adjacency list is more space efficient.
Key Takeaways
In this blog we have learned about the famous graph algorithm, the Bellman-Ford algorithm, we have seen its dry run, and in the end, we have also seen Bellman’s Ford implementation in Java.
Also, check out the other algorithms based on graphs like Floyd Warshall Algorithm, Prim's Algorithm, Kruskal's Algorithm, Dijkstra's Algorithm, etc. Now that you know the various algorithms based on graphs, try out some questions on our CodeStudio Platform!
Check out this problem - Frog Jump
We hope this article has helped you in some way and if you liked our article, do upvote our article and help other ninjas grow. You can refer to our Guided Path on CodeStudio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more!
Head over to our practice platform CodeStudio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!
