C++ Dijkstra Algorithm Using the Priority Queue

In this article we will be finding the shortest routes from a source vertex in a graph to all vertices in the graph, given a graph and a source vertex in the graph:

// Program to find Dijkstra's shortest path using
// priority_queue in STL
#include < bits/stdc++.h >
#incliude < stdlib>
using namespace std ;
# define INF 0x3f3f3f3f


// iPair ==> Integer Pair
typedef pair < int , int > iPair ;


// This class represents a directed graph using
// adjacency list representation
class Graph
{
	int V ; // No. of vertices


	// In a weighted graph, we need to store vertex
	// and weight pair for every edge
	list < pair < int , int > > * adj ;


public :
	Graph ( int V ) ; // Creating Constructor of class Graph


	// Add an edge to a graph with this function
	void addedge ( int u , int v , int w ) ;


	// calculating the shortest route from s
	void shortestPath ( int s ) ;
} ;


// Memory is allocated for the adjacency list.
Graph : : Graph (int V )
{
	this -> V = V ;
	adj = new list < iPair > [ V ] ;
}


void Graph : : addedge ( int u , int v , int w )
{
	adj [ u ] . push_back ( make_pair ( v , w ) ) ;
	adj [ v ] . push_back ( make_pair ( u , w ) ) ;
}


// The shortest routes from src to all other vertices are printed. 
void Graph : : shortestPath ( int src )
{
	// Make a priority queue for storing vertices that
	// are being preprocessed
	priority_queue < iPair , vector < iPair > , greater < iPair > > pq ;


	//  Create a distance vector and initialise it.
	// distances as infinite ( INF )
	vector < int > dist ( V , INF ) ;


	// Insert source itself in priority queue and initialize
	// its distance as 0.
	pq.push ( make_pair ( 0 , src ) ) ;
	dist [ src ] = 0 ;


	/* Looping till priority queue becomes empty (or all
	distances are not finalized) */
	while ( !pq.empty ( ) )
	{
		// The first vertex in pair is the minimum distance
		// vertex, extract it from priority queue.
		// vertex label is stored in second of pair (it
		// has to be done this way to keep the vertices
		// sorted distance (distance must be first item
		// in pair)
		int u = pq.top ( ) . second ;
		pq.pop ( ) ;


		// 'i' is used to get all adjacent vertices of a vertex
		list < pair < int , int > > : : iterator i ;
		for ( i = adj [ u ] . begin ( ) ; i != adj [ u ] . end ( ) ; ++i )
		{
			// Get vertex label and weight of current adjacent
			// of u.
			int v = ( * i ) . first ;
			int weight = ( * i ) . second ;


			// If there is a shorter way to v through u.
			if ( dist [ v ] > dist [ u ] + weight )
			{
				// Updating distance of v
				dist [ v ] = dist [ u ] + weight ;
				pq.push ( make_pair ( dist [ v ] , v ) ) ;
			}
		}
	}


	// Print the shortest distances in dist [ ]
	printf ( "Vertex Distance from Source\n" ) ;
	for ( int i = 0 ; i < V ; ++i )
		printf ( "%d \ t \ t %d \n" , i , dist [ i ] ) ;
}
// Test methods of graph class with a driver application.
int main ( )
{
	// Create the graph shown in the figure above.
	int V = 9 ;
	Graph g ( V ) ;


	// making above shown graph
	g.addedge ( 0 , 1 , 4 ) ;
	g.addedge ( 0 , 7 , 8 ) ;
	g.addedge ( 1 , 2 , 8 ) ;
	g.addedge ( 1 , 7 , 11 ) ;
	g.addedge ( 2 , 3 , 7 ) ;
	g.addedge ( 2 , 8 , 2 ) ;
	g.addedge ( 2 , 5 , 4 ) ;
	g.addedge ( 3 , 4 , 9 ) ;
	g.addedge ( 3 , 5 , 14 ) ;
	g.addedge ( 4 , 5 , 10 ) ;
	g.addedge ( 5 , 6 , 2 ) ;
	g.addedge ( 6 , 7 , 1 ) ;
	g.addedge ( 6 , 8 , 6 ) ;
	g.addedge ( 7 , 8 , 7 ) ;


	g.shortestPath ( 0 ) ;


	return 0 ;
}

OUTPUT:

Vertex   Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14
……………………………………………
Process executed in 0.31 seconds
Press any key to continue

Explanation:

• The second version is simpler in terms of temporal complexity, but it is quite sophisticated since we have created our own priority queue. Because it employs STL, the third implementation is the simplest.
• The problem with the third method is that it use set, which employs Self-Balancing Binary Search Trees.
• The heap (or priority queue) is always suggested for Dijkstra's method since the needed actions (extract minimum and reduce key) fit the heap's expertise (or priority queue). The issue is that the decrease key is not supported by the priority queue.
• To fix the problem, don't update the key; instead, make a new duplicate of it. As a result, several occurrences of the same vertex are allowed in the priority queue.
• This method does not necessitate a reduction in critical operations and has the following important qualities.

Another method is to express weighted graphs as vectors.

#include < bits/stdc++.h >
#include < isotream >
#include < stdlib >
using namespace std ;
# define INF 0x3f3f3f3f


// iPair ==> Integer Pair
typedef pair < int , int > iPair ; 
// To add an edge
void addedge ( vector < pair < int , int > > adj [ ] , int u , int v , int wt )
{
	adj [ u ] . push_back ( make_pair ( v , wt ) ) ;
	adj [ v ] . push_back ( make_pair ( u , wt ) ) ;
}
// The shortest routes from src to all other vertices are printed.
void shortestPath (vector < pair < int , int > > adj [ ] , int V , int src )
{
	priority_queue< iPair, vector <iPair> , greater<iPair> > pq; 
	// Create a vector for distances and initialize all
	// distances as infinite (INF)
	vector < int > dist ( V , INF ) ; 
	// Insert source itself in priority queue and initialize
	// its distance as 0.
	pq.push ( make_pair ( 0 , src ) ) ;
	dist [ src ] = 0 ; 
	/* Looping till priority queue becomes empty (or all
	distances are not finalized) */
	while ( ! pq.empty ( ) )
	{
		// The first vertex in pair is the minimum distance
		// vertex, extract it from priority queue.
		// vertex label is stored in second of pair (it
		// has to be done this way to keep the vertices
		// sorted distance (distance must be first item
		// in pair)
		int u = pq.top ( ) .second ;
		pq.pop ( ) ; 
		// Get all adjacent of u.
		for ( auto x : adj [ u ] )
		{
			// Get vertex label and weight of current adjacent
			// of u.
			int v = x.first ;
			int weight = x.second ; 
			// If there is shorted path to v through u.
			if ( dist [ v ] > dist [ u ] + weight )
			{
				// Updating distance of v
				dist [ v ] = dist [ u ] + weight ;
				pq.push ( make_pair ( dist [ v ] , v ) ) ;
			}
		}
	}
	// Print shortest distances stored in dist [ ]
	printf ( "Vertex Distance from Source\n" ) ;
	for ( int i = 0 ; i < V ; ++i )
		printf ( "%d \ t \ t %d \n" , i , dist [ i ] ) ;
}
// Driver program to test methods of graph class
int main ( )
{
	int V = 9 ;
	vector < iPair > adj [  V  ]  ; 
	// making above shown graph
	addedge ( adj , 0 , 1 , 4 ) ;
	addedge ( adj , 0 , 7 , 8 ) ;
	addedge ( adj , 1 , 2 , 8 ) ;
	addedge ( adj , 1 , 7 , 11 ) ;
	addedge ( adj , 2 , 3 , 7 ) ;
	addedge ( adj , 2 , 8 , 2 ) ;
	addedge ( adj , 2 , 5 , 4 ) ;
	addedge ( adj , 3 , 4 , 9 ) ;
	addedge ( adj , 3 , 5 , 14 ) ;
	addedge ( adj , 4 , 5 , 10 ) ;
	addedge ( adj , 5 , 6 , 2 ) ;
	addedge ( adj , 6 , 7 , 1 ) ;
	addedge ( adj , 6 , 8 , 6 ) ; 
	addedge ( adj , 7 , 8 , 7 ) ;


	shortestPath ( adj , V , 0 ) ;


	return 0 ;
}

OUTPUT:

Vertex Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14
…………………………………………….
Process executed in 0.11 seconds
Press any key to continue.

Explanation:

The heap (or priority queue) is always suggested for Dijkstra's method since the needed actions (extract minimum and reduce key) fit the heap's expertise (or priority queue). The issue is that priority queue does not support the decrease key. To fix the problem, don't update the key; instead, make a new duplicate of it. As a result, several occurrences of the same vertex are allowed in the priority queue.