C++ Program to Implement Dijkstra’s Algorithm Using Priority Queue

by

Dijkstra’s algorithm is a popular algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. In this article, we will learn to code a C++ Program to Implement Dijkstra’s Algorithm Using Priority Queue and show how to implement it using a priority queue in C++. We will present a complete program along with detailed explanations and example outputs.

Introduction

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph. The algorithm uses a priority queue to greedily select the next node with the smallest tentative distance.

Prerequisites

To follow along with this article, you should have:

  • A basic understanding of C++ programming.
  • Familiarity with graphs and priority queues (heaps).
  • A C++ compiler to compile and run the programs.

Dijkstra’s Algorithm

Definition

Given a graph GGG with vertices VVV and edges EEE, and a source node sss, Dijkstra’s algorithm computes the shortest path from sss to all other nodes in GGG.

Steps

  1. Initialize distances from the source to all vertices as infinity and distance to the source itself as 0.
  2. Insert the source vertex into a priority queue.
  3. While the priority queue is not empty:
    • Extract the vertex with the minimum distance.
    • For each neighbor of this vertex, calculate the distance from the source and update it if it is smaller than the current known distance.

Example Implementation

Let’s implement Dijkstra’s algorithm using a priority queue in C++.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>

using namespace std;

typedef pair<int, int> pii;

void dijkstra(const vector<vector<pii>>& graph, int source) {
    int V = graph.size();
    vector<int> dist(V, INT_MAX);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[source] = 0;
    pq.push(make_pair(0, source));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (const auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    cout << "Vertex \t Distance from Source" << endl;
    for (int i = 0; i < V; ++i) {
        cout << i << " \t " << dist[i] << endl;
    }
}

int main() {
    int V, E;
    cout << "Enter number of vertices: ";
    cin >> V;
    cout << "Enter number of edges: ";
    cin >> E;

    vector<vector<pii>> graph(V);
    cout << "Enter edges (u, v, w) - from node u to v with weight w:" << endl;
    for (int i = 0; i < E; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w)); // If the graph is undirected
    }

    int source;
    cout << "Enter source vertex: ";
    cin >> source;

    dijkstra(graph, source);

    return 0;
}

Explanation

  1. Graph Representation: The graph is represented using an adjacency list where each node points to a list of pairs. Each pair contains a neighboring node and the weight of the edge connecting them.
  2. Priority Queue: A priority queue (min-heap) is used to efficiently fetch the next node with the smallest tentative distance.
  3. Dijkstra Function:
    • Initialize distances with INT_MAX and the distance to the source node as 0.
    • Push the source node into the priority queue.
    • While the priority queue is not empty:
      • Extract the node with the minimum distance.
      • For each neighbor, calculate the tentative distance and update it if it is smaller than the current known distance.
      • Push the neighbor into the priority queue with the updated distance.
  4. Main Function:
    • Reads the number of vertices and edges.
    • Reads each edge and constructs the graph.
    • Calls the dijkstra function with the source node.
    • Prints the shortest distances from the source node to all other nodes.

Output

Example run with the following input:

Enter number of vertices: 5
Enter number of edges: 6
Enter edges (u, v, w) - from node u to v with weight w:
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 1
Enter source vertex: 0

Output:

Vertex   Distance from Source
0        0
1        2
2        3
3        9
4        6

Conclusion

In this article, we explored Dijkstra’s algorithm and its implementation using a priority queue in C++