Start learning free

LESSON 336 OF 343 · GRAPHS

Dijkstra's Algorithm in C++: Shortest Paths with a Priority Queue

Practice Priority Queue, O((V+E) log V) Read the full explanation

Given a weighted undirected graph with n vertices (labeled 0 to n-1) and a list of edges where edges[i] = [u, v, weight], find the shortest distance from vertex 0 to every other vertex using Dijkstra's algorithm.

Return an array dist of length n where dist[i] is the shortest distance from vertex 0 to vertex i. All vertices are reachable.

Example

Input: n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]
Output: [0, 3, 1, 4, 7]
Explanation:
- 0 → 0: distance 0
- 0 → 2 → 1: distance 1 + 2 = 3
- 0 → 2: distance 1
- 0 → 2 → 1 → 3: distance 1 + 2 + 1 = 4
- 0 → 2 → 1 → 3 → 4: distance 1 + 2 + 1 + 3 = 7

Constraints

2 <= n <= 1000
1 <= edges.length <= 5000
0 <= u, v < n
1 <= weight <= 1000
The graph is connected.

STEP 1 OF 10

Guided

Ctrl + Enter to check

C++ · GRAPHS

Dijkstra in C++, explained

Problem overview

The method dijkstra receives n, the number of vertices labelled 0 to n - 1, and a vector edges of triples [u, v, weight]. Each triple is an undirected edge between u and v with a positive weight. The method returns a vector dist where dist[i] is the length of the shortest path from vertex 0 to vertex i, measured as the sum of the weights. The graph is connected, so every vertex can be reached.

For n = 5 and edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]] the answer is [0, 3, 1, 4, 7]. The direct edge from 0 to 1 costs 4, but going 0 to 2 to 1 costs 1 + 2 = 3. Vertex 3 is best reached through 2 and 1, at 1 + 2 + 1 = 4, and vertex 4 adds 3 more.

Approach: always settle the closest unsettled vertex

Breadth-first search finds the fewest edges, but with weights the path with fewer edges isn't always cheaper. Dijkstra's algorithm handles weights, provided none is negative, with one idea: keep the best distance found so far for every vertex, and always expand the vertex whose best distance is smallest.

Why is that safe? Take the unexpanded vertex with the smallest tentative distance. Any other route to it must pass through some unexpanded vertex first, and every such vertex is at least as far away, with non-negative weights added on top. So no other route can be shorter, and the distance is final.

Expanding a vertex means relaxing its edges: for each edge from u to v with weight w, if dist[u] + w is less than the current dist[v], then a better route to v has been found, and dist[v] is updated.

To find "the unexpanded vertex with the smallest distance" quickly, use a priority queue (a heap) of pairs (distance, vertex). The standard C++ priority queue has no way to lower the priority of an existing entry. The usual workaround is lazy deletion: when a distance improves, push a new entry and leave the old one in place. When an outdated entry comes out, its stored distance is larger than the current one, so it is skipped.

Step by step

Build the adjacency list adj, a vector<vector<pair<int,int>>> of size n. The entry for vertex u is a list of (neighbour, weight) pairs.
Fill it from edges with auto& e. The graph is undirected, so each edge is stored twice: {e[1], e[2]} in adj[e[0]] and {e[0], e[2]} in adj[e[1]].
Initialise dist with n copies of INT_MAX, meaning "not reached yet", and set dist[0] to 0.
Create the priority queue pq of pair<int,int> and push {0, 0}: distance 0, vertex 0. Passing greater makes the smallest distance come out first.
Loop while pq is not empty.
Take the smallest entry into d and u with auto [d, u], then call pq.pop().
Skip stale entries. If d > dist[u], a shorter path to u was found after this entry was queued, and u has already been handled with that better distance. Use continue.
Visit each neighbour with for (auto& [v, w] : adj[u]).
Relax. If dist[u] + w < dist[v], set dist[v] to that sum and push {dist[v], v}. Only queue an entry when the distance really improves, or the queue fills with useless entries.
Return dist. When the queue is empty, no further improvement is possible.

The solution in C++

class Solution {
public:
    vector<int> dijkstra(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int,int>>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back({e[1], e[2]});
            adj[e[1]].push_back({e[0], e[2]});
        }
        vector<int> dist(n, INT_MAX);
        dist[0] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) {
                continue;
            }
            for (auto& [v, w] : adj[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    }
};

The C++ details worth knowing:

A max-heap by default. priority_queue<T> puts the largest element on top. The three template arguments pair<int,int>, vector<pair<int,int>> and greater<pair<int,int>> name the element type, the container underneath and the comparison, which flips the order so the smallest comes out first. In C++17 this long form is the standard way to write a min-heap.
Pairs compare lexicographically. A pair is ordered by its first member and then by its second, so putting the distance first means the heap orders by distance. Ties are broken by vertex number, which doesn't matter here.
top() and pop() are separate. auto [d, u] = pq.top(); copies the pair into two named variables, so the later pop() is safe.
Structured bindings in loops. for (auto& [v, w] : adj[u]) unpacks each (neighbour, weight) pair by reference, without copying.
INT_MAX and overflow. Adding to INT_MAX would be signed overflow, which is undefined behaviour. The code never does it, because only vertices that were already reached are expanded, so dist[u] is always a real distance. The largest real distance is under 1,000 edges times 1,000, about one million, so int is comfortable.
continue in the loop jumps straight to the next iteration, skipping the expansion of a stale entry.

Complexity

Time: O((n + m) log m), where m is the number of edges. Each successful relaxation pushes one entry, and there can be at most one per directed edge, so the queue never holds more than 2m + 1 entries. Each push and pop costs O(log m). Every vertex is expanded with its final distance once, and the stale copies are discarded in constant time after their pop.

Space: O(n + m). The adjacency list stores each edge twice, and the queue holds up to O(m) entries.

Edge cases and common mistakes

Negative weights. The algorithm assumes none. Here weights are at least 1. With a negative edge, a vertex already settled could later get a shorter route, and the result would be wrong.
Forgetting the second direction. The edges are undirected. Storing each edge only from e[0] to e[1] would miss paths that cross it the other way.
Using the default heap. Without greater, the largest distance is processed first. The result can still come out right, but the running time becomes far worse.
Skipping the stale check. The answer stays correct without it, but each outdated entry would be expanded again and the work could grow a lot.
Pushing on every edge. The relaxation test guards the push. Pushing unconditionally floods the queue.
Parallel edges. If two edges connect the same vertices, relaxation keeps the cheaper one automatically.
Unreachable vertices. This lesson guarantees there are none. If there were, those entries would keep INT_MAX.

Testing

n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]] gives [0, 3, 1, 4, 7].
n = 2, edges = [[0,1,7]] gives [0, 7].
n = 3, edges = [[0,1,1],[1,2,1],[0,2,5]] gives [0, 1, 2]: the two-edge route beats the heavy direct edge.

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free