Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Bellman Ford algorithm
3.
Problem Statement
4.
Algorithm
4.1.
Pseudocode
4.2.
Dry Run
5.
Implementation in Java
5.1.
Complexity Analysis
6.
Implementation in C++
6.1.
Complexity Analysis
7.
Why (N-1) iterations?
8.
Does it work for negative cycles?
9.
Frequently Asked Questions
9.1.
Is the Bellman Ford algorithm faster than the Dijkstra algorithm?
9.2.
In the Bellman Ford algorithm, why is the source vertex path set to 0 and the other vertices path to the maximum value?
9.3.
How is the Dijkstra algorithm different when compared to the Bellman Ford algorithm?
9.4.
List all the shortest path algorithms.
9.5.
Which is a more space-efficient adjacency list or adjacency matrix?
10.
Key Takeaways
Last Updated: Mar 27, 2024
Medium

Bellman Ford Algorithm

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

OG Image

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. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

dry run 1

 

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:

dry run 2

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,
 

dry run 3

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.

dry run 4

Implementation in Java

Let's see how the Bellman Ford algorithm is implemented in Java. 

Recommended: Please try to solve the "Bellman-Ford algorithm" on "CODESTUDIO" first before moving on to the solution. 

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: 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);
}

 

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

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.

Reason for N-1 Iterations

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.

Negative cycles fail

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 AlgorithmPrim's AlgorithmKruskal's Algorithm, Dijkstra's Algorithm, etc. Now that you know the various algorithms based on graphs, try out some questions on our Coding Ninjas Studio 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 Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem Design, and many more!

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!

Previous article
Dijkstra's Algorithm
Next article
Floyd Warshall Algorithm
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass