Dijkstra's Algorithm in C++ with a Priority Queue

Breadth-first search finds shortest paths when every edge has the same length. As soon as edges have different weights, such as road lengths or travel times, BFS gives wrong answers. Dijkstra's algorithm is the standard fix for graphs whose edge weights are non-negative.

The problem

There are n cities and m one-way flights, each with a cost. Find the cheapest cost from city 1 to every city. This is CSES 1671 – Shortest Routes I, with n up to 10⁵ and m up to 2 × 10⁵.

The idea

Keep a tentative distance for every node, starting at 0 for the source and infinity for the rest. Then repeat:

1. Take the unfinished node u with the smallest tentative distance. That distance is now final.
2. For every edge u → v with weight w, check whether going through u is cheaper: if dist[u] + w < dist[v], update dist[v]. This is called relaxing the edge.

Why the smallest node is final

Suppose u has the smallest tentative distance d. Any other route to u would have to leave the set of finished nodes through some unfinished node, whose distance is already at least d. Adding more edges can only make that route longer, because weights are non-negative. So no route can beat d.

That argument is exactly where negative edges break things: a negative edge could make a longer-looking path cheaper later. With negative weights, use Bellman–Ford instead.

Finding the minimum quickly

Scanning all nodes for the minimum each time is O(n²). A min-heap (priority_queue with greater<>) gives the smallest entry in O(log n). Whenever we improve a distance, we push the new (distance, node) pair.

A node can end up in the heap several times with older, larger distances. Instead of deleting those, we simply skip any entry whose distance does not match the current dist[u]. These are called stale entries.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});   // directed edge a -> b with weight w
    }

    const long long INF = LLONG_MAX;
    vector<long long> dist(n + 1, INF);
    // min-heap of (distance, node)
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;          // stale entry, skip it
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << dist[i] << (i == n ? '\n' : ' ');
    return 0;
}

Example

3 4
1 2 6
1 3 2
3 2 3
1 3 4

The direct flight 1 → 2 costs 6, but 1 → 3 → 2 costs 2 + 3 = 5. Output: 0 5 2.

Step by step: pop city 1 (distance 0) and relax its edges, so city 2 gets 6 and city 3 gets 2. Pop city 3 (distance 2) and relax 3 → 2, improving city 2 to 5. Pop city 2 (distance 5). The old entry (6, city 2) is popped later and skipped as stale.

Complexity

Each edge can push at most one entry, so the heap holds O(m) entries. Total time is O((n + m) log m), and memory is O(n + m).

Common mistakes

• Using a max-heap. C++'s priority_queue returns the largest element by default. Use greater<>, or push negative distances.
• Forgetting the stale check. Without if (d != dist[u]) continue; the answer is still correct, but on some graphs the algorithm becomes much slower.
• Using int distances. A path of 10⁵ edges with weight 10⁹ each sums to 10¹⁴. Use long long.
• Undirected graphs. If roads go both ways, add each edge in both directions.

Practice problems

• CSES 1671 – Shortest Routes I: the problem in this post.
• Codeforces 20C – Dijkstra?: also print the path itself, by storing each node's parent when you relax an edge.

If BFS is still new to you, start with the BFS deep dive. Dijkstra is the same idea with a priority queue in place of a plain queue.