Dijkstra’s Algorithm in C++

Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a single source node to all other nodes in a graph. It works efficiently with graphs that have non-negative weights.

1. How Dijkstra’s Algorithm Works

• Step 1: Initialize distances from the source to all other nodes as infinity (∞), except for the source itself, which is set to 0.
• Step 2: Use a priority queue (min-heap) to always process the node with the smallest distance first.
• Step 3: Relax all adjacent edges of the selected node, updating their distances if a shorter path is found.
• Step 4: Repeat until all nodes have been processed.

2. C++ Implementation of Dijkstra’s Algorithm

Here’s the complete C++ implementation of Dijkstra’s Algorithm using an adjacency list and a priority queue (min-heap).

Code Example

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

using namespace std;

// Define a pair for the priority queue (distance, node)
typedef pair<int, int> pii;

// Dijkstra's Algorithm Function
vector<int> dijkstra(int V, vector<vector<pii>>& adj, int src) {
    // Min-heap to store (distance, node)
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    // Distance array initialized to "infinity"
    vector<int> dist(V, INT_MAX);
    
    // Start from the source node
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        int currDist = pq.top().first; // Current node distance
        int node = pq.top().second;    // Current node
        pq.pop();

        // If the current distance is greater than the stored distance, skip it
        if (currDist > dist[node]) continue;

        // Explore all adjacent nodes
        for (auto& neighbor : adj[node]) {
            int nextNode = neighbor.first;
            int weight = neighbor.second;

            // Relaxation step: If a shorter path is found
            if (dist[node] + weight < dist[nextNode]) {
                dist[nextNode] = dist[node] + weight;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }

    return dist;
}

int main() {
    int V = 5; // Number of vertices
    vector<vector<pii>> adj(V);

    // Graph Representation (Adjacency List)
    // Example Graph:
    // 0 --(10)--> 1
    // 0 --(3)--> 3
    // 1 --(2)--> 2
    // 3 --(1)--> 1
    // 3 --(8)--> 4
    // 4 --(4)--> 2
    adj[0].push_back({1, 10});
    adj[0].push_back({3, 3});
    adj[1].push_back({2, 2});
    adj[3].push_back({1, 1});
    adj[3].push_back({4, 8});
    adj[4].push_back({2, 4});

    int source = 0; // Start node
    vector<int> shortestPaths = dijkstra(V, adj, source);

    // Output the shortest paths
    cout << "Shortest distances from source node " << source << ":\n";
    for (int i = 0; i < V; i++) {
        cout << "Node " << i << " : " << shortestPaths[i] << endl;
    }

    return 0;
}

3. Code Explanation

Step-by-Step Breakdown

1. Graph Representation:
   • We use an adjacency list where adj[i] stores a list of (neighbor, weight) pairs.
   • This keeps memory usage efficient (O(V + E) instead of O(V²) for an adjacency matrix).
2. Priority Queue (Min-Heap):
   • A min-heap is used to always process the nearest unvisited node first.
   • The priority queue stores (distance, node) pairs, sorted by the smallest distance.
3. Distance Initialization:
   • We initialize all distances as INT_MAX (infinity).
   • The source node’s distance is set to 0, as it is the starting point.
4. Processing the Nodes (Main Loop):
   • Extract the node with the smallest distance from the queue.
   • Relax all its neighbors: If a shorter path is found, update the distance and push the node back into the queue.
5. Final Output:
   • The algorithm outputs the shortest distance from the source node to all other nodes.

4. Time Complexity Analysis

• Efficient for large graphs with non-negative weights.
• Performs well with sparse graphs (E ≈ V).

5. Example Output

For the given graph, running the program produces:

Shortest distances from source node 0:
Node 0 : 0
Node 1 : 4
Node 2 : 6
Node 3 : 3
Node 4 : 11

Explanation:

• 0 → 3 → 1 (3 + 1 = 4) is shorter than 0 → 1 (10).
• 0 → 3 → 1 → 2 (3 + 1 + 2 = 6).
• 0 → 3 → 4 (3 + 8 = 11).