Bellman Ford Algorithm

quiz
Challenge Inside! : Find out where you stand! Try quiz, solve problems & win rewards!

Overview

The Bellman-Ford algorithm is an example of Dynamic Programming. It starts with a starting vertex and calculates the distances of other vertices which can be reached by one edge. It then continues to find a path with two edges and so on. The Bellman-Ford algorithm follows the bottom-up approach.

Scope

  • This article tells about the working of the Bellman-Ford algorithm.
  • Difference between Dijkstra’s and Bellman Ford’s Algorithm.
  • Explanation of Bellman Ford Algorithm.
  • Complexity of Bellman Ford Algorithm.




Takeaways

  • Complexity of Bellman Ford Algorithm
    • Time complexity O(V.E)O(V.E).

Introduction

Suppose that we are going for a picnic, there may be some path leading to the picnic spot where we have to pay taxes and some paths which have houses of our relatives/friends who will give us gifts if we pass by their home. To find the optimal path (path with the least cost) from home to picnic spot we need Bellman Ford Algorithm.

Bellman ford algorithm is used to calculate the shortest paths from a single source vertex to all vertices in the graph. This algorithm also works on graphs with a negative edge weight cycle (It is a cycle of edges with weights that sums to a negative number), unlike Dijkstra which gives wrong answers for the shortest path between two vertices.

Bellman Ford algorithm is easier to implement when compared to dijkstra algorithm and optimal for distributed systems. (but on the other hand, it has a high time complexity i.e. O(VE)O(VE) where V and E are numbers of vertices and edges respectively.

Example of Bellman Ford Algorithm

Suppose that we have a graph consisting of 5 vertices having edges between them as shown in the picture below. Now, we want to find shortest distance to each vertex vi 0<i<6 starting from the vertex 1.

example of bellman ford algorithm

After performing bellman ford algorithm on the above graph the output array would look like - Shortest_Distance = [0, 3, 5, 2, 5]

Where each index 'í' of array denotes the shortest distance of the ith vertex from 1st vertex, 1<=i<=5.

How Bellman Ford Algorithm Works?

Input:

  • A 2D Array/List denoting edges and their respective weights.
  • A src vertex.

Output: An array where each index denotes the shortest path length between that vertex and src vertex.

Procedure:

  1. In this step, we would declare an array of size V(Number of vertexes) say dis[] and initialize with all of its indexes with a very big Value (preferably INT_MAX) except src which will be initialized with value 0. We are doing this because initially we assume that it takes infinite time to reach any of the vertices from our source vertex and we are initializing dis[src]=0 because we are already on source vertex.

  2. In this step, the shortest distance is calculated. For it, we would do the underlying step V-1 times. For every edge u→v make dis[v]=min(dis[u]+ wt of edge u→v, dis[v]) It means whenever we are on any vertex u we will check if we can reach any of its neighbors in less time it is currently possible to visit, we will update the dis[v] to dis[u]+wt of edge u→v.

  3. In this step, we will check if there exists a negative edge weight cycle traversing each and every edge u→v and checking if there exists dis[u] + wt of edge u→v < dis[v] then our graph contains a negative edge weight cycle because traversing the edges again and again is beneficial as it is lowering the cost to traverse the graph.

Explanation of Bellman Ford Example

Difference between Dijkstra's and Bellman Ford's Algorithm

Bellman Ford AlgorithmDijkstra Algorithm
Its implementation is inspired by the dynamic programming approach.Its implementation is inspired by the greedy approach.
It is easier to implement in a distributive way.It is quite complex to implement in a distributed way.
It also works when the given graph contains a negative edge weight cycle.It fails if a graph contains a negative edge weight cycle.
It's is more time consuming than Dijkstra's. It's Time complexity is O(VE)It's Time complexity is O(ELogV)

Pesudocode

BellmanFord(Edges[][], src, V): 
    dis[] = new int[V]
 
    For i = 1 to V :
        dis[i] = INF     // (INF=Very Large Value)

    dis[src] = 0
    For i = 1 to V-1 :
        For j 1 to Edges.length:
        u = Edges[j][0]
        v = Edges[j][1]
        wt = Edges[j][2]
        dis[v] = MIN(dis[u]+wt,dis[v])

    For i = 1 to Edges.length:
        u = Edges[i][0]
        v = Edges[i][1]
        wt = Edges[i][2]
        If(dis[v] > dis[u]+wt)
            Print "Negative Weight cycle exists."

    Return dis

Codes Implementation of Bellman Ford Algorithm

  • C/C++ Implementation of Bellman Ford

vector<int> bellmanFord(vector<vector<int>>,int src, int V){
    
    // Step 1 - Creating a V sized array/vector,
    // and initializing it with a very big value.
    
    vector<int> dis(V,INT_MAX); // Creating a vector dis of size V with values as INT_MAX.
    dis[src] = 0; // Since we are already on source vertex, we can reach it within no time.
    
    // Step 2 - For V-1 times, traversing over,
    // all the edges and checking if a shorter
    // path between any edge u to v is possible. 
    int u,v,wt;
    for(int i=0;i<V-1;i++) // Iterating V-1 times 
    {
        for(int j=0;j<edges.size();j++) // Iterating over all the edges. 
        {
            u = edges[j][0]; // Source vertex.
            v = edges[j][1]; // Destination vertex.
            wt = edges[j][2];// Weight of the edge. 
            
            // If we can reach v from u in less time it 
            // is currently required to reach v then update 
            // the value.
            if(dis[u]!=INT_MAX && dis[v] > dis[u] + wt)
                dis[v] = dis[u] + wt;
        }
    }
    
    // Step 3 - Checking for negative edge weight cycle, 
    // by checking if the underliying condition satifies.
    for(int j=0;j<edges.size();j++)
    {
        u = edges[j][0];
        v = edges[j][1];
        wt = edges[j][2];
        // If the below condition satisfies, it means negative 
        // edge weight cycle exists. Because traversing again 
        // is reducing the cost and in order to minimize the 
        // cost we can traverse till infinity and hence a proper 
        // answer can't be calculated. 
        if(dis[u]!=INT_MAX && dis[v] > dis[u] + wt)
            return {};
    }
    return dis; // returning our answer vector/array.
}
  • Java Implementation of Bellman Ford

int[] bellmanFord(int edges[][],int V,int src){
    
    // Step 1 - Creating a V sized array/list,
    // and initializing it with a very big value.
    
    // Creating a vector dis of size V with values as INT_MAX.
    int dis[]=new int[V];
    Arrays.fill(dis,Integer.MAX_VALUE);
    
    dis[src]=0; // Since we are already on source vertex, we can reach it within no time.
    
    // Step 2 - For V-1 times, traversing over,
    // all the edges and checking if a shorter
    // path between any edge u to v is possible. 
    int u,v,wt;
    for(int i=0;i<n-1;i++)  // Iterating V-1 times 
    {
        for(int j=0;j<edges.length;j++) // Iterating over all the edges. 
        {
            u=edges[j][0]; // Source vertex.
            v=edges[j][1]; // Destination vertex.
            wt=edges[j][2];// Weight of the edge. 
            
            // If we can reach v from u in less time it 
            // is currently required to reach v then update 
            // the value.
            if(dis[u]!=Integer.MAX_VALUE&&dis[u]+wt<dis[v])
            dis[v]=dis[u]+wt;
        }
    }
    
    // Step 3 - Checking for negative edge weight cycle, 
    // by checking if the underliying condition satifies.
    for(int j=0;j<edges.length;j++)
    {
        u=edges[j][0];
        v=edges[j][1];
        wt=edges[j][2];
        
        // If the below condition satisfies, it means negative 
        // edge weight cycle exists. Because traversing again 
        // is reducing the cost and in order to minimize the 
        // cost we can traverse till infinity and hence a proper 
        // answer can't be calculated. 
        if(dis[u]!=Integer.MAX_VALUE&&dis[u]+wt<dis[v])
        return new int[0];
    }
    
    return dis; // returning our answer vector/array.
}
  • Python Implementation of Bellman Ford

def bellmanFord(V,edges,src):
    
    # Step 1 - Creating a V sized array/list,
    # and initializing it with a very big value.
    INF=999999999
    dis=[INF for x in range(V)]
    
    dis[src]=0 # Since we are already on source vertex, we can reach it within no time.
    
    # Step 2 - For V-1 times, traversing over,
    # all the edges and checking if a shorter
    # path between any edge u to v is possible. 
    
    for i in range(V-1): # Iterating V-1 times 
        for j in range(len(edges)): #  Iterating over all the edges. 
            u=edges[j][0]; # Source vertex
            v=edges[j][1]; # destination vertex
            wt=edges[j][2]; # weight of edge from u to v
            
            # If we can reach v from u in less time it 
            # is currently required to reach v then update 
            # the value.
            if(dis[u]!=INF and dis[u]+wt<dis[v]):
                dis[v]=dis[u]+wt
                
    # Step 3 - Checking for negative edge weight cycle, 
    # by checking if the underliying condition satifies.
    for i in range(len(edges)):
        u=edges[i][0];
        v=edges[i][1];
        wt=edges[i][2];
        
        # If the below condition satisfies, it means negative 
        # edge weight cycle exists. Because traversing again 
        # is reducing the cost and in order to minimize the 
        # cost we can traverse till infinity and hence a proper 
        # answer can't be calculated. 
        if(dis[u]!=INF and dis[u]+wt<dis[v]):
            return []
    return dis # Return our answer array/list

Complexity Analysis of Bellman Ford

  • Time Complexity -

    Since we are traversing all the edges V-1 times, and each time we are traversing all the E vertices, therefore the time complexity is O(V.E).

  • Space Complexity -

    Since we are using an auxiliary array dis of size V, the space complexity is O(V).

    Where V and E are numbers of vertices and edges respectively.

Bonus Tip of Bellman Ford

The algorithm can be speeded up further because in most of the cases we get our final answer after performing step 2 few times only. Because dis array stops getting updated after some steps, So traversing edges again and again is nothing but waste of time.

To check wether any value of dis gets updated in any given iteration, we can keep a flag in the outer loop of Step 2 and if it not changed in the inner for loop then we can exit from the loop becuase we have already got our answer.

Though the modification will not change the asymptotic nature of the algorithm because in some graphs we will need all the V-1 steps to be done. But it will optmize the run time of algorithm in a "average case" i.e. random graphs.

The minor modification need to be done in step 2 is given below -

for(int i=0;i<n-1;i++)
{
    boolean flag=true;
    for(int j=0;j<edges.length;j++)
    {
        u=edges[j][0]; // Source vertex
        v=edges[j][1]; // Destination vertex
        wt=edges[j][2];// wight of edge from u to v.
        
        // If we can reach v from u in less time it 
        // is currently required to reach v then update 
        // the value.
        if(dis[u]!=Integer.MAX_VALUE&&dis[u]+wt<dis[v])
        {
            dis[v]=dis[u]+wt;
            
            // Make flag false since we have entered in 
            // the if conditon which maens there will be 
            // at least one updation in next araay.
            flag=false;
        }
    }
    // If flag is still true it means 
    // condition did not satisfied even once.
    if(flag)
        break;
}

Though the average case Time Complexity would be - O(V.E) but in the best case it can be done in only O(E) time. Think of the case in which we get out of the loop after the very first or second step.

Applications

  • Checking for negative edge weight cycle.
  • For finding shortest path of all vertices from single source.
  • Routing Algorithms.

Conclusion

  • In this blog, we have discussed one of the most important graph algorithms i.e. Bellman-Ford algorithm which is used to find the shortest path to all vertices from a single source vertex in O(VE) time complexity.
  • It can find shortest distance of all vertices from single source. It can also detect if there exists a negative edge weight cycle in the given graph. Therefore, it also finds its way in many routing techniques.
  • If you want to upskill yourself in Data Structures and algorithms then do checkout, Scaler where you will get live lectures, assignments, and regular tests from the people working in your dream company.
Challenge Time!
quiz
quiz
Time to test your skills and win rewards! Note: Rewards will be credited after the next product update.
Free Courses by top Scaler instructors
certificate icon
Certificates
Data Structures Tutorial
This program includes modules that cover the basics to advance constructs of Data Structures Tutorial. The highly interactive and curated modules are designed to help you become a master of this language.'
If you’re a learning enthusiast, this is for you.
Module Certificate
Criteria
Upon successful completion of all the modules in the hub, you will be eligible for a certificate.
You need to sign in, in the beginning, to track your progress and get your certificate.
rcbGet a Free personalized Career Roadmap from