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, 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

  1. 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;
    }

    • 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 😉

  2. 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!! 🙂

    • 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! 🙂

    • That’s unexpected! Can you comment your input here? My input is –

      6 9
      1 4 4
      2 1 2
      2 4 -2
      2 3 4
      3 5 2
      4 5 -1
      4 6 1
      5 2 2
      6 5 -2
      1
      

      That’s for a graph with negative cycle. And input graph without a negative cycle would be –

      6 9
      1 4 4
      2 1 2
      2 4 4
      2 3 4
      3 5 2
      4 5 2
      4 6 1
      5 2 2
      6 5 -2
      1
      

      Try the above given code for these inputs and let me know if you face any more issues.

  3. Pingback: shortest paths in graph | programmingalgos

Leave a Reply