C++ Program for Dijkstra Algorithm with Example

A C++ program for Dijkstra algorithm uses a graph represented by adjacency matrix and finds shortest paths from a source using dist[] array and visited[] flags, updating distances with the minimum found so far.

Examples

InputGraph with 4 nodes and edges: 0->1(1), 0->2(4), 1->2(2), 1->3(6), 2->3(3), source=0

OutputShortest distances from node 0: 0 1 3 6

InputGraph with 3 nodes and edges: 0->1(5), 1->2(10), source=0

OutputShortest distances from node 0: 0 5 15

InputGraph with 2 nodes and no edges, source=0

OutputShortest distances from node 0: 0 INF

How to Think About It

To solve this, think of the graph as cities connected by roads with distances. Start from the source city, mark its distance as zero, and all others as infinity. Repeatedly pick the closest unvisited city, update the distances to its neighbors if shorter paths are found, and mark it visited. Continue until all cities are visited.

Algorithm

1

Initialize distances from source to all nodes as infinity except source itself which is zero.

2

Create a visited set to track nodes whose shortest distance is finalized.

3

Repeat until all nodes are visited:

4

Pick the unvisited node with the smallest distance.

5

Update distances of its neighbors if a shorter path is found through this node.

6

Mark the picked node as visited.

Code

cpp

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

void dijkstra(const vector<vector<int>>& graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    dist[src] = 0;

    for (int i = 0; i < n - 1; ++i) {
        int u = -1;
        int minDist = INF;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) break;
        visited[u] = true;

        for (int v = 0; v < n; ++v) {
            if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    cout << "Shortest distances from node " << src << ": ";
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) cout << "INF ";
        else cout << dist[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<vector<int>> graph = {
        {0, 1, 4, 0},
        {0, 0, 2, 6},
        {0, 0, 0, 3},
        {0, 0, 0, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

Output

Shortest distances from node 0: 0 1 3 6 

Dry Run

Let's trace the example graph with 4 nodes and source 0 through the code.

1

Initialization

dist = [0, INF, INF, INF], visited = [false, false, false, false]

2

First iteration - pick node 0

u = 0 (min dist 0), visited = [true, false, false, false] Update neighbors: Node 1: dist[1] = min(INF, 0+1) = 1 Node 2: dist[2] = min(INF, 0+4) = 4

3

Second iteration - pick node 1

u = 1 (min dist 1), visited = [true, true, false, false] Update neighbors: Node 2: dist[2] = min(4, 1+2) = 3 Node 3: dist[3] = min(INF, 1+6) = 7

4

Third iteration - pick node 2

u = 2 (min dist 3), visited = [true, true, true, false] Update neighbors: Node 3: dist[3] = min(7, 3+3) = 6

5

Fourth iteration - pick node 3

u = 3 (min dist 6), visited = [true, true, true, true] No neighbors to update.

Iteration	Picked Node	dist array	visited array
1	0	[0, INF, INF, INF]	[true, false, false, false]
2	1	[0, 1, 4, INF]	[true, true, false, false]
3	2	[0, 1, 3, 7]	[true, true, true, false]
4	3	[0, 1, 3, 6]	[true, true, true, true]

Why This Works

Step 1: Initialize distances

Set all distances to infinity except the source node which is zero to start from there.

Step 2: Select closest unvisited node

Pick the node with the smallest current distance that is not yet visited to ensure shortest path progress.

Step 3: Update neighbors

For each neighbor of the selected node, update its distance if a shorter path is found through the selected node.

Step 4: Repeat until all nodes visited

Continue selecting nodes and updating distances until all nodes have their shortest distance finalized.

Alternative Approaches

Using priority queue (min-heap)

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

void dijkstra_pq(const vector<vector<pair<int,int>>>& graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INF);
    dist[src] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d > dist[u]) continue;
        for (auto& edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "Shortest distances from node " << src << ": ";
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) cout << "INF ";
        else cout << dist[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<vector<pair<int,int>>> graph = {
        {{1,1}, {2,4}},
        {{2,2}, {3,6}},
        {{3,3}},
        {}
    };
    dijkstra_pq(graph, 0);
    return 0;
}

This approach is faster for sparse graphs with many nodes because it uses a priority queue to pick the closest node efficiently.

Using adjacency list without priority queue

cpp

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();

void dijkstra_list(const vector<vector<pair<int,int>>>& graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    dist[src] = 0;

    for (int i = 0; i < n - 1; ++i) {
        int u = -1, minDist = INF;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u == -1) break;
        visited[u] = true;

        for (auto& edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (!visited[v] && dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    cout << "Shortest distances from node " << src << ": ";
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INF) cout << "INF ";
        else cout << dist[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<vector<pair<int,int>>> graph = {
        {{1,1}, {2,4}},
        {{2,2}, {3,6}},
        {{3,3}},
        {}
    };
    dijkstra_list(graph, 0);
    return 0;
}

This is simpler but less efficient than using a priority queue, suitable for small graphs.

Complexity: O(V^2) for adjacency matrix, O((V+E) log V) with priority queue time, O(V^2) for adjacency matrix, O(V+E) for adjacency list space

Time Complexity

Using an adjacency matrix, the algorithm checks all nodes for the minimum distance in each iteration, leading to O(V^2). Using a priority queue with adjacency list reduces this to O((V+E) log V) by efficiently selecting the next node.

Space Complexity

Adjacency matrix requires O(V^2) space to store all edges, while adjacency list uses O(V+E), which is more efficient for sparse graphs.

Which Approach is Fastest?

For dense graphs, adjacency matrix with simple loops is fine. For large sparse graphs, priority queue with adjacency list is faster and more memory efficient.

Approach	Time	Space	Best For
Adjacency Matrix	O(V^2)	O(V^2)	Small or dense graphs
Adjacency List + Priority Queue	O((V+E) log V)	O(V+E)	Large or sparse graphs
Adjacency List without PQ	O(V^2)	O(V+E)	Small graphs, simpler code