Bellman Ford Algorithm using Dynamic Programming

This is a C++ Program that Solves Bellman Ford Algorithm using Dynamic Programming technique.

Problem Description

Given a weighted graph and a source vertex. Find the shortest path from the source to all the vertices. The graph may contain edges with negative value.

Problem Solution

This is a single source shortest path problem. We know that this problem can be solved using Djikstra’s Algorithm. But if the graph has negative weight edges, Djikstra’s Algo cannot be applied there. For that we have Bellman Ford Algorithm.

However, if the graph has negative weight loop, it is reported. This is because due to a negative weight cycle, the shortest distance for the vertices in the loop will keep on decreasing infinitely.

We create a distance array dist[]. dist[i]=minimum distance of vertex i from source vertex.

dist[src]=0

Now, compute the dist values for all the vertices in bottom up fashion for V-1 passes(V=no. of vertices). After this we have the min. dist values in the table for all vertices. At this point we will check for negative weight cycle. We iterate the calculation of dist values one more time, and if any value is reduced, we will know that there is a negative loop in the graph.

Expected Input and Output

Case-1:

 
number of vertices=5
number of edges=6
 
Information of all edges(source, destination, weight)
1 2 2
2 3 3
3 4 4
4 5 5
 
Source vertex=1
 
Expected Result: 
vectex    Min. distance from source
1         0
2         2
3         5
4         9
5         14

Case-2:

 
number of vertices=5
number of edges=7
 
Information of all edges(source, destination, weight)
 
1 2 17
2 3 25
3 4 1
4 2 -24
2 5 15
1 4 40
5 3 9
 
Source vertex=1
 
Expected Result: 
vectex    Min. distance from source
1         0
2         16
3         40
4         40
5         31

Case-3:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
number of vertices=5
number of edges=6
 
Information of all edges(source, destination, weight)
1 2 6 
2 5 1
2 4 5
1 4 4
3 2 -4
5 3 2
 
Source vertex=1
 
Expected Result: There is a negative weight loop in the graph

Program/Source Code

Here is source code of the C++ Program for Bellman Ford Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
 
```
```
//Bellman Ford Algorithm
```
```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```

//every edge has 3 values associated with it source, destination and weight

```
struct edge
```
```
{
```
```
    int s,d,w;
```
```
};
```
```
 
```

int bellmanFord(int n, int e, int src, vector<edge> &edge, vector<int> &dist)

```
{
```
```
    int i,j;
```
```
    int s,d,w;
```
```
 
```
```
    i=src;
```
```
 
```
```
    dist[i-1]=0;
```
```
 
```
```
    //n-1 passes
```
```
    for(i=1;i<n;i++)
```
```
    {
```
```
        //for each edge
```
```
        for(j=0;j<e;j++)
```
```
        {
```
```
            s=edge[j].s;
```
```
            d=edge[j].d;
```
```
            w=edge[j].w;
```
```
 
```

            //if we can get a smaller value of dist[d] using this edge, replace it

            if(dist[s]!=INT_MAX && dist[s]+w<dist[d])

```
            {
```
```
                dist[d]=dist[s]+w;
```
```
            }
```
```
        }
```
```
    }
```
```
 
```

    //this loop is to detect a negative loop

```
    for(j=0;j<e;j++)
```
```
    {
```
```
        s=edge[i].s;
```
```
        d=edge[i].d;
```
```
        w=edge[i].w;
```
```
 
```

        if(dist[s]!=INT_MAX && dist[s]+w<dist[d])

```
        {
```

            //we have caught a negative loop

```
            return 0;
```
```
        }
```
```
    }
```
```
 
```
```
    //all okay signal
```
```
    //indicating no negative loop
```
```
    return 1;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i;
```
```
    int n,e;
```
```
    int s,d,w;
```
```
    int src;
```
```
 
```

    cout<<"Enter the number of vertices ";

```
    cin>>n;
```
```
 
```
```
    cout<<"Enter the number of edges ";
```
```
    cin>>e;
```
```
 
```
```
    vector<edge> edge(e);
```
```
 
```

    cout<<"Enter the src, dest and weight of each edge"<<endl;

```
    for(i=0;i<e;i++)
```
```
    {
```
```
        cin>>s>>d>>edge[i].w;
```
```
        edge[i].s=s-1;
```
```
        edge[i].d=d-1;
```
```
    }
```
```
 
```
```
    cout<<"Enter the source vertex ";
```
```
    cin>>src;
```
```
 
```
```
 
```

    //create a vector of size n(for n vertices) and initialize the value of each element to infinity

    //dist[i]=the minimum distance of vertex i from source vertex

```
    vector<int> dist(n,INT_MAX);
```
```
 
```
```
    i=bellmanFord(n,e,src,edge,dist);
```
```
 
```
```
    cout<<endl;
```
```
 
```
```
    if(i)
```
```
    {
```

        cout<<"vectex      Min. distance from source"<<endl;

```
        for(i=0;i<n;i++)
```
```
        {
```

            cout<<i+1<<"         "<<dist[i]<<endl;

```
        }
```
```
    }
```
```
 
```
```
    else
```
```
    {
```
```
        //negative loop
```

        cout<<"There is a negative weight loop in the graph "<<endl;

```
    }
```
```
 
```
```
    return 0;
```
```
}
```

Program Explanation

The information of all the edges are stored in the nodes of a structure edge. In the main function, we take the inputs for number of vertices, number of edges and information of edge(source, destination and weight).

Then the function BellmanFord() is invoked which will calculate the shortest path for all vertices from the source. If a negative weight cycle is found, it is reported. Otherwise the distance array is displayed.

Runtime Test Cases

 
Case-1:
$ g++ bellman_ford.cpp
$ ./a.out
Enter the number of vertices 5
Enter the number of edges 4
Enter the src, dest and weight of each edge
1 2 2
2 3 3
3 4 4
4 5 5
Enter the source vertex 1
 
vectex    Min. distance from source
1         0
2         2
3         5
4         9
5         14
 
Case-2:
$ ./a.out
Enter the number of vertices 5
Enter the number of edges 7
Enter the src, dest and weight of each edge
1 2 17
2 3 25
3 4 1
4 2 -24
2 5 15
1 4 40
5 3 9
Enter the source vertex 1
 
vectex    Min. distance from source
1         0
2         16
3         40
4         40
5         31
 
Case-3:
$ ./a.out
Enter the number of vertices 5
Enter the number of edges 6
Enter the src, dest and weight of each edge
1 2 6 
2 5 1
2 4 5
1 4 4
3 2 -4
5 3 2
Enter the source vertex 1
 
There is a negative weight loop in the graph

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

If you find any mistake above, kindly email to [email protected]

« Prev - Make Palindrome Problem – Dynamic Programming Solutions

» Next - Floyd Warshall Algorithm using Dynamic Programming

Related Posts:

Recommended Articles: