# Bellman Ford Algorithm using C++ STL

Hello people..! This is a special extension to my post on Bellman Ford Algorithm. Here, I give you a different implementation of Bellman Ford Algorithm which uses 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|)
// covering one edge once, so the runtime of the code in this
// block is O(|E|)

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) {

// 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
}

for (int i = 1; i < adjacencyList.size(); ++i) {

list< pair<int, int> >::iterator itr = adjacencyList[i].begin();

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..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practising..! Happy Coding..! 😀