This is a C++ Program that Solves Bellman Ford Algorithm using Dynamic Programming technique.
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.
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.
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:
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
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;
}
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.
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.
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Programming Books
- Practice Design & Analysis of Algorithms MCQ
- Apply for Computer Science Internship