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

Advertisements