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 Algorithm, 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.
Idea Behind Bellman-Ford Algorithm
The Bellman-Ford algorithm is designed to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It is particularly effective for graphs that may contain negative weight edges. The algorithm systematically updates the shortest path estimates, ensuring that the final path lengths reflect the minimal distances from the source. This is achieved through a series of edge relaxations, iteratively improving the estimates until the optimal paths are determined.
Principle of Relaxation of Edges for Bellman-Ford
Relaxation Process: For each edge, the algorithm checks if the known distance to the destination can be shortened by going through the source vertex.
Distance Update: If the current shortest distance to the destination vertex is greater than the distance to the source plus the edge's weight, the distance is updated.
Iterative Improvement: This relaxation process is repeated for all edges, gradually refining the shortest path estimates.
Total Iterations: The relaxation occurs for a total of V−1V - 1V−1 iterations, where VVV is the number of vertices.
Why Relaxing Edges N-1 Times Gives Us Single Source Shortest Path?
Relaxing edges N−1 times ensures that the shortest paths are found for all vertices that can be reached within N−1 edges. Since the longest possible simple path in a graph with N vertices has at most N−1 edges, performing the relaxation process this many times guarantees that all shortest paths from the source are identified. After N−1 iterations, any further updates would indicate either optimal paths or the presence of negative cycles.
Why Does the Reduction of Distance in the N’th Relaxation Indicate the Existence of a Negative Cycle?
If a distance to a vertex can still be reduced after N−1 relaxations, it implies that there is a negative weight cycle reachable from the source. This is because, in a correctly functioning algorithm, all shortest paths would have been established by the N−1 iterations. Thus, further reduction of any distance suggests that the path can be made shorter indefinitely by traversing the negative cycle.
Working of Bellman-Ford Algorithm to Detect the Negative Cycle in the Graph
The Bellman-Ford algorithm proceeds by first initializing distances from the source to all vertices. After N−11 relaxations, a final iteration checks all edges again. If any distance can still be updated, it indicates the presence of a negative cycle. This process allows the algorithm to not only find the shortest paths but also verify the integrity of those paths concerning negative weight cycles.
Algorithm to Find Negative Cycle in a Directed Weighted Graph Using Bellman-Ford
Initialization: Set the distance to the source to 0 and all other vertices to infinity.
Relaxation: For N−1 iterations, relax all edges.
Cycle Detection: In a subsequent pass, if any edge can still be relaxed, identify the cycle.
Example: In a graph with vertices A, B, and C, with edges A -> B (weight 1), B -> C (weight -2), and C -> A (weight -1), running the algorithm would show a negative cycle through the repeated relaxation process.
Handling Disconnected Graphs in the Algorithm
The Bellman-Ford algorithm can effectively handle disconnected graphs by initializing distances to unreachable vertices as infinity. During the relaxation phase, only reachable vertices will have their distances updated. After the algorithm completes, the final distance values will indicate which vertices are accessible from the source and which are not.
Example: In a disconnected graph where vertex D is isolated from A, B, and C, the algorithm will set the distance to D as infinity while correctly calculating distances to the other vertices.
Complexity Analysis of Bellman-Ford Algorithm
The Bellman-Ford algorithm has a time complexity of O(V⋅E) where V is the number of vertices and E is the number of edges. This arises from the necessity of performing the relaxation process for all edges across V−1 iterations.
Example: In a graph with 5 vertices and 10 edges, the algorithm will require up to 40 operations, making it less efficient than Dijkstra's algorithm for graphs without negative weights but more versatile for graphs with negative edges or cycles.
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
You can also try this code with Online Java Compiler
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);
}
}
You can also try this code with Online Java Compiler
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: 3
Complexity 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);
}
You can also try this code with Online C++ Compiler
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: 3
You can also try this code with Online C++ Compiler
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.
Bellman-Ford’s Algorithm Applications
Routing Protocols: Used in network routing protocols like RIP (Routing Information Protocol) to find the shortest path in networks.
Graph Analysis: Suitable for graphs with negative weight edges, allowing analysis of various transportation and communication networks.
Game Development: Helps in determining the shortest path in game environments with weighted edges representing movement costs.
Financial Modeling: Applied in scenarios where negative weights might represent financial losses or penalties in investment models.
Artificial Intelligence: Utilized in AI algorithms for pathfinding in environments with complex weights.
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.
Conclusion
In this blog, we explored the widely recognized Bellman-Ford algorithm, exploring its mechanics through a detailed dry run. Additionally, we provided a practical implementation of the Bellman-Ford algorithm in Java, demonstrating its effectiveness in solving shortest path problems in graphs.
46+ registered 