C++ Dijkstra Algorithm Using The Priority Queue

In this article, we will see the implementation of the Dijkstra algorithm using the priority queue of C++ STL. Dijkstra algorithm is used to find the shortest path from the source to the destination in an undirected graph.

A graph having weight on the edges is given as below:

Let us consider a source vertex 0, we have to find the shortest path from the source vertex to all the vertices in the graph.

Source vertex = 0

Create graph structure

We will create a class Graph with data members as

• ✅ int v - To store the number of vertices in the graph
• ✅ List of pairs - To store the vertex and the weight associated with a particular vertex.

list > *adj;

Constructors:

We need a constructor to allocate the memory of the adjacency list.

Graph(int vertex)
	{
		this->V = vertex; // Allocate the number of vertices 
		adj = list<pair> [vertex]; // Allocate memory for adjacency list 
	}

How to add an edge to the graph?

The list of pairs created has two arguments. One will contain the vertex, and the other will contain the weight associated with it.

As the graph is bidirectional, we can add the same weight to the opposite vertex.

Code:

void addanEdge(int u, int v, int w)
{
	adj[u].push_back(make_pair(v,w)); // add v to w 
	adj[v].push_back(make_pair(u,w)); add w to v 
// To add a vertex with weight associated with it 
}

Algorithm

• ✅ Mark initial distance from the source is infinite.
• ✅ Create an empty priority_queue PQ. Every item of PQ is a pair (weight, vertex). Weight (or distance) is used as the first item of pair as the first item is by default used to compare two pairs.
• ✅ Insert source vertex into PQ and make its distance as 0.
• ✅ Until the priority queue defined as PQ does not become empty. Perform the operations a and b. Extract minimum distance vertex from PQ and let it be u. Loop through all adjacent of u and do Following for every vertex v. // If there is a shorter path to v // through u. If dist[v] > dist[u] + weight(u, v) // distance of ( v) > distance of (u) and weight from u to v Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v) Insert v into the pq (Even if v is already there)
• ✅ Loop through the dist array to print the shortest paths from source to all the vertices.
• ✅ Extract minimum distance vertex from PQ and let it be u.
• ✅ Loop through all adjacent of u and do Following for every vertex v. // If there is a shorter path to v // through u. If dist[v] > dist[u] + weight(u, v) // distance of ( v) > distance of (u) and weight from u to v Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v) Insert v into the pq (Even if v is already there)
• ✅ Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v)
• ✅ Insert v into the pq (Even if v is already there)

C++ code

Example
Copy
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f // The distance to other vertices is initialized as infinite
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
class Graph // Graph structure
    {
    int V; // No. of vertices in the graph
    list<pair<int, int>>* adj; // the list of pair to store vertex and its weight
public:
    // Constructor that accept number of vertices in graph
    Graph(int V) // allocate the vertex memory
    {
        this->V = V; // assign the vertex 
        adj = new list<iPair>[V]; // allocate space for vertices 
    }
    void addEdge(int u, int v, int w); // add edges in the graph
    // prints shortest path from s
    void shortestPathingraph(int s); // pass source vertex
};
void Graph::addEdge(int u, int v, int w) // add an edge
{
    adj[u].push_back(make_pair(v, w)); // make a pair of vertex and weight and // add it to the list
    adj[v].push_back(make_pair(u, w)); // add oppositely by making a pair of weight and vertex
}
// Calling function outside the Graph class
void Graph::shortestPathingraph(int src) // src is the source vertex
{
    // Create a priority queue to store vertices that
    // are being preprocessed.
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    vector<int> dist(V, INF); // All distance from source are infinite
    pq.push(make_pair(0, src)); // push spurce node into the queue
    dist[src] = 0; // distance of source will be always 0
    while (!pq.empty()) { // While queue is not empty
        // Extract the first minimum distance from the priority queue
        // vertex label is stored in second of pair (it
        // has to be done this way to keep the vertices
        // sorted distance
        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 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));
            }
        }
    }
    printf("Vertex \tDistance from Source\n"); // Print the result
    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]); // The shortest distance from source
}
int main()
{
    int V = 9; // vertices in given graph are 9
    Graph g(V); //  call Constructor by creating an object of graph
    g.addEdge(0, 1, 4); // add root node with neighour vertex and weight
    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.shortestPathingraph(0); // call the function to find shortest path of graph
    return 0; // end of main function()
}
Try it Yourself

Output

Vertex   Distance from Source
0 		   0
1 		   4
2 		  12
3 		  19
4 		  21
5 		  11
6 		   9
7 	           8
8 		  14