Hello people..! This is a special extension to my post on Bellman Ford Algorithm. Here, I give you a different implementation, Bellman Ford Algorithm using C++ STL. Some of the features of this code are –
- The Adjacency List used is exactly as in Adjacency List using C++ STL.
- The Bellman Ford algorithm function uses C++ reference parameters to yield the necessary results.
- The shortestDistances array is now a vector of pairs.
- It prints the vertices of negative cycle if the algorithm detects one.
/*
* Bellman-Ford Algorithm
* using C++ STL
*
* Authored by,
* Vamsi Sangam
*
*/
#include <cstdio>
#include <climits>
#include <vector>
#include <list>
#include <utility>
using namespace std;
void PrintNegativeCycle(vector< pair<int, int> > shortestDistances, int vertex, int startVertex)
{
if (vertex == startVertex) {
printf("%d ", vertex);
} else if (shortestDistances[vertex].second == 0) {
PrintNegativeCycle(shortestDistances, startVertex, startVertex);
printf("%d ", vertex);
} else {
PrintNegativeCycle(shortestDistances, shortestDistances[vertex].second, startVertex);
printf("%d ", vertex);
}
}
// Bellman-Ford Algorithm which takes the Adjacency List, starting vertex,
// and an empty shortestDistances vector as input. It applies the algorithm
// and keeps filling values into shortestDistances which is a reference
// parameter. It returns true if there are no negative edges, and vice-versa.
int bellmanFord(
vector< list< pair<int, int> > > adjacencyList,
int vertices,
int startVertex,
vector< pair<int, int> > & shortestDistances
)
{
list< pair<int, int> >::iterator traverse;
int i, j, k;
// Initialisation
for (i = 0; i <= vertices; ++i) {
shortestDistances[i].first = INT_MAX;
shortestDistances[i].second = -1;
}
// Setting distance to source = 0
shortestDistances[startVertex].first = 0;
shortestDistances[startVertex].second = 0;
// The Algorithm that computes Shortest Distances
for (i = 1; i <= vertices - 1; ++i) { // Runs 'vertices - 1' times = O(|V|)
for (j = 1; j <= vertices; ++j) { // Runs as many times as the edges = O(|E|)
// The code ahead basically explores the whole of Adjcency List,
// covering one edge once, so the runtime of the code in this
// block is O(|E|)
traverse = adjacencyList[j].begin();
while (traverse != adjacencyList[j].end()) {
if (shortestDistances[j].first == INT_MAX) {
// Important...!
//traverse = traverse->next;
++traverse;
continue;
}
// Checking for Relaxation
if ((*traverse).second + shortestDistances[j].first <
shortestDistances[(*traverse).first].first) {
// Relaxation
shortestDistances[(*traverse).first].first = (*traverse).second
+ shortestDistances[j].first;
shortestDistances[(*traverse).first].second = j;
}
++traverse;
}
}
}
// Checking for Negative Cycles
for (j = 1; j <= vertices; ++j) {
traverse = adjacencyList[j].begin();
while (traverse != adjacencyList[j].end()) {
// Checking for further relaxation
if ((*traverse).second + shortestDistances[j].first <
shortestDistances[(*traverse).first].first) {
// Negative Cycle found as further relaxation is possible
return j;
}
++traverse;
}
}
return -1;
}
int main()
{
int vertices, edges, v1, v2, weight;
printf("Enter the Number of Vertices -\n");
scanf("%d", &vertices);
printf("Enter the Number of Edges -\n");
scanf("%d", &edges);
// Adjacency List is a vector of list.
// Where each element is a pair<int, int>
// pair.first -> the edge's destination
// pair.second -> edge's weight
vector< list< pair<int, int> > > adjacencyList(vertices + 1);
printf("Enter the Edges V1 -> V2, of weight W\n");
for (int i = 1; i <= edges; ++i) {
scanf("%d%d%d", &v1, &v2, &weight);
// Adding Edge to the Directed Graph
adjacencyList[v1].push_back(make_pair(v2, weight));
}
printf("\nThe Adjacency List-\n");
// Printing Adjacency List
for (int i = 1; i < adjacencyList.size(); ++i) {
printf("adjacencyList[%d] ", i);
list< pair<int, int> >::iterator itr = adjacencyList[i].begin();
while (itr != adjacencyList[i].end()) {
printf(" -> %d(%d)", (*itr).first, (*itr).second);
++itr;
}
printf("\n");
}
vector< pair<int, int> > shortestDistances(vertices + 1);
// shortestDistances is a vector of pairs
// pair.first -> the shortest distance from start vertex
// pair.second -> parent vertex in the shortest path
int startVertex;
printf("\nEnter a Start Vertex -\n");
scanf("%d", &startVertex);
int returnValue = bellmanFord(adjacencyList, vertices, startVertex, shortestDistances);
if (returnValue == -1) {
printf("No Negative Cycles exist in the Graph -\n");
} else {
printf("Negative Cycles exists in the Graph -\n");
// The Bellman-Ford Algorithm does not work with negative cycles,
// all it can do is merely detect them, so when a negative cycle
// is detected, the shortestDistances vector has wrong values
PrintNegativeCycle(shortestDistances, shortestDistances[returnValue].second
, returnValue);
return 0;
}
printf("\n\nVertex Shortest Distance to Vertex %d Parent Vertex-\n", startVertex);
for (int i = 1; i <= vertices; ++i) {
printf("%d \t %d \t\t\t\t %d\n", i, shortestDistances[i].first,
shortestDistances[i].second);
}
return 0;
}
Keep comparing every strange line with the simple C++ code… I’m sure you’ll get it..! 🙂 … Feel free to comment if you have any doubts..! Keep practising..! Happy Coding..! 😀
16 thoughts on “Bellman Ford Algorithm using C++ STL”
Complexity your program is O(|V|^2.|E|) because you are using first loop unnecessarily. The edited code with complexity O(|V|.|E|) is below
==================================================================================================
/*
* Bellman-Ford Algorithm
* using C++ STL
*
* Authored by,
* Vamsi Sangam
*
* Edited by,
* ALOK SHAKYA
*
*/
#include
#include
#include
#include
#include
using namespace std;
void PrintNegativeCycle(vector< pair > shortestDistances, int vertex, int startVertex)
{
if (vertex == startVertex) {
printf(“%d “, vertex);
} else if (shortestDistances[vertex].second == 0) {
PrintNegativeCycle(shortestDistances, startVertex, startVertex);
printf(“%d “, vertex);
} else {
PrintNegativeCycle(shortestDistances, shortestDistances[vertex].second, startVertex);
printf(“%d “, vertex);
}
}
// Bellman-Ford Algorithm which takes the Adjacency List, starting vertex,
// and an empty shortestDistances vector as input. It applies the algorithm
// and keeps filling values into shortestDistances which is a reference
// parameter. It returns true if there are no negative edges, and vice-versa.
int bellmanFord(
vector< list< pair > > adjacencyList,
int vertices,
int startVertex,
vector< pair > & shortestDistances
)
{
list< pair >::iterator traverse;
int i, j, k;
// Initialisation
for (i = 0; i <= vertices; ++i) {
shortestDistances[i].first = INT_MAX;
shortestDistances[i].second = -1;
}
// Setting distance to source = 0
shortestDistances[startVertex].first = 0;
shortestDistances[startVertex].second = 0;
// The Algorithm that computes Shortest Distances
// Runs 'vertices – 1' times = O(|V|)
for (j = 1; j next;
++traverse;
continue;
}
// Checking for Relaxation
if ((*traverse).second + shortestDistances[j].first <
shortestDistances[(*traverse).first].first) {
// Relaxation
shortestDistances[(*traverse).first].first = (*traverse).second
+ shortestDistances[j].first;
shortestDistances[(*traverse).first].second = j;
}
++traverse;
}
}
// Checking for Negative Cycles
for (j = 1; j <= vertices; ++j) {
traverse = adjacencyList[j].begin();
while (traverse != adjacencyList[j].end()) {
// Checking for further relaxation
if ((*traverse).second + shortestDistances[j].first <
shortestDistances[(*traverse).first].first) {
// Negative Cycle found as further relaxation is possible
return j;
}
++traverse;
}
}
return -1;
}
int main()
{
int vertices, edges, v1, v2, weight;
printf("Enter the Number of Vertices -\n");
scanf("%d", &vertices);
printf("Enter the Number of Edges -\n");
scanf("%d", &edges);
// Adjacency List is a vector of list.
// Where each element is a pair
// pair.first -> the edge’s destination
// pair.second -> edge’s weight
vector< list< pair > > adjacencyList(vertices + 1);
printf(“Enter the Edges V1 -> V2, of weight W\n”);
for (int i = 1; i <= edges; ++i) {
scanf("%d%d%d", &v1, &v2, &weight);
// Adding Edge to the Directed Graph
adjacencyList[v1].push_back(make_pair(v2, weight));
}
printf("\nThe Adjacency List-\n");
// Printing Adjacency List
for (int i = 1; i < adjacencyList.size(); ++i) {
printf("adjacencyList[%d] ", i);
list< pair >::iterator itr = adjacencyList[i].begin();
while (itr != adjacencyList[i].end()) {
printf(” -> %d(%d)”, (*itr).first, (*itr).second);
++itr;
}
printf(“\n”);
}
vector< pair > shortestDistances(vertices + 1);
// shortestDistances is a vector of pairs
// pair.first -> the shortest distance from start vertex
// pair.second -> parent vertex in the shortest path
int startVertex;
printf(“\nEnter a Start Vertex -\n”);
scanf(“%d”, &startVertex);
int returnValue = bellmanFord(adjacencyList, vertices, startVertex, shortestDistances);
if (returnValue == -1) {
printf(“No Negative Cycles exist in the Graph -\n”);
} else {
printf(“Negative Cycles exists in the Graph -\n”);
// The Bellman-Ford Algorithm does not work with negative cycles,
// all it can do is merely detect them, so when a negative cycle
// is detected, the shortestDistances vector has wrong values
PrintNegativeCycle(shortestDistances, shortestDistances[returnValue].second
, returnValue);
return 0;
}
printf(“\n\nVertex Shortest Distance to Vertex %d Parent Vertex-\n”, startVertex);
for (int i = 1; i <= vertices; ++i) {
printf("%d \t %d \t\t\t\t %d\n", i, shortestDistances[i].first,
shortestDistances[i].second);
}
return 0;
}
Please correct me if I am wrong. I am new to programming. Thanks for providing good code using STL to learn.
Can you plz explain line from 18 to 29..
It prints the negative cycle… To do that what we are doing in this function is that, we take any one vertex of the negative cycle and recursively look at it’s parent… We will keep looking at the parent until the parent turns out to be the same vertex with which we started with (we have looped once through the cycle)… Thus printing all the vertices in the cycle… In terms of code, the first if condition checks if the vertex is the same vertex with which we began our function… The second if condition is a special where the vertex is the source vertex of the bellman ford (remember in bellman ford, we assign the source vertex’s parent to be none).. Third if condition recursively looks at a vertex’s parent… Remember that “shortestDistances[vertex].second” is the parent of “vertex” … Give it a little though, I’m sure you’ll get it 😉
Please how can I make this code accept negative decimal numbers as the weights in the graph
You can do that by simply making the pair as …. So your adjacency list will be vector< list< pair > > 🙂
Hi Vamsi,
First of all..great code You have written!!!
I have a question..how can I expand Your code to let the program choose automatically numbers for the number of vertices and edges, and also to create a matrix automatically by itself?
Thank You so far!! 🙂
Can you explain while loop in line 99 to 104
Did you mean while loop in line 90-99?… The while loop in line 90-99 checks for negative cycle… The way the algorithm works is that you basically try to perform relaxation for |V| – 1 times… Until then, you should have got all your shortest paths… You try to relax the edges one more time… Which is what the while loop in line 90-99 is trying to do… If you are able to do relaxation, then it means you have a negative cycle in your graph… Try to give it a little thought, I’m sure you’ll get it! 🙂
i need your help, can you give me a hand?
Sure! Drop me a mail at vamsisangam@live.com 🙂
when i was executing your code, this came out: bellman-ford has stopped working!
That’s unexpected! Can you comment your input here? My input is –
That’s for a graph with negative cycle. And input graph without a negative cycle would be –
Try the above given code for these inputs and let me know if you face any more issues.
Thank you for your explanation
My Pleasure 🙂