Dijkstra

BFS finds shortest paths when every edge costs 1. The moment edges carry different weights, BFS collapses. Dijkstra's algorithm fixes this with one elegant idea: always process the closest unfinished node. That greedy choice, backed by a priority queue, solves single-source shortest paths in \(O((V + E) \log V)\) — fast enough for graphs with millions of edges.

The Core Idea: Relaxation

Dijkstra shortest path tree with distances from source

Edge relaxation: if going through u is shorter, update dist to v

Relaxation is the atomic operation of every shortest-path algorithm. Given an edge \((u, v)\) with weight \(w\):

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

You found a shorter route to \(v\) by going through \(u\). Update the estimate. That's it. Dijkstra, Bellman-Ford, and Floyd-Warshall all differ only in the order they relax edges.

Dijkstra's order is greedy: relax edges out of the node with the smallest tentative distance first.

The Algorithm

Dijkstra's algorithm step by step with priority queue states

Set dist[source] = 0, all others to \(\infty\).
Push (0, source) into a min-heap.
Pop the smallest (d, u). If d > dist[u], skip it (stale entry).
For each neighbor (v, w) of u: relax the edge. If improved, push (dist[v], v).
Repeat until the heap is empty.

vector<long long> dist(n + 1, LLONG_MAX);
dist[1] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
pq.push({0, 1});

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

Key insight. The if (d > dist[u]) continue line is lazy deletion. We don't remove old entries from the heap when a distance improves — we just push a new one and skip stale pops. This avoids the complexity of decrease-key and works perfectly in practice.

Full Trace

Graph with 5 nodes, source = 1:

1 --2-- 2 --3-- 5
|       |
4       1
|       |
3 --5-- 4

Edges: 1→2 (2), 1→3 (4), 2→4 (1), 2→5 (3), 3→4 (5), 4→5 (2).

Step	Pop (d, u)	dist[] after relaxation	PQ contents
Init	—	[0, ∞, ∞, ∞, ∞]	{(0,1)}
1	(0, 1)	[0, 2, 4, ∞, ∞]	{(2,2), (4,3)}
2	(2, 2)	[0, 2, 4, 3, 5]	{(3,4), (4,3), (5,5)}
3	(3, 4)	[0, 2, 4, 3, 5]	{(4,3), (5,5)}
4	(4, 3)	[0, 2, 4, 3, 5]	{(5,5)}
5	(5, 5)	[0, 2, 4, 3, 5]	{}

Final distances from node 1: [0, 2, 4, 3, 5].

Notice step 3: when we pop node 4, we try to relax edge 4→5 with cost \(3 + 2 = 5\). But dist[5] is already 5 from step 2. No improvement. The greedy choice of processing the closest node first means we never have to go back and fix a finalized node.

Why It Works: The Greedy Proof

Claim: When node \(u\) is popped from the PQ, dist[u] equals the true shortest distance.

Proof sketch. Suppose not. Then some shorter path to \(u\) exists that goes through an unfinished node \(x\). But \(x\) is unfinished, so dist[x] >= dist[u] (we popped \(u\) first). The path through \(x\) has length \(\geq\) dist[x] + (something non-negative) \(\geq\) dist[u]. Contradiction — it's not shorter.

Gotcha. The proof relies on "something non-negative." If edges can be negative, a longer path through \(x\) might actually be shorter because it picks up a negative edge later. This is exactly why Dijkstra fails with negative weights — Chapter 5, Lesson 2.

CSES Shortest Routes I

Problem: Directed weighted graph, \(N\) nodes, \(M\) edges. Find shortest paths from node 1 to all nodes.

This is the textbook Dijkstra application. Watch the constraints: \(N \leq 10^5\), \(M \leq 2 \times 10^5\), weights up to \(10^9\). Distances can overflow int — use long long.

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

int main() {
    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 c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    vector<long long> dist(n + 1, LLONG_MAX);
    dist[1] = 0;
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    pq.push({0, 1});

    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});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];
}

Common Pitfalls

1. Forgetting Lazy Deletion

Without the if (d > dist[u]) continue check, you process stale entries. The algorithm still gives correct answers but degrades to \(O(E \log E)\) in the worst case with many redundant relaxations. Always include the check.

2. Using `int` for Distances

With weights up to \(10^9\) and paths of length up to \(10^5\) edges, the maximum distance is \(10^{14}\). That overflows a 32-bit integer. Use long long and initialize to LLONG_MAX.

3. Max-Heap Instead of Min-Heap

C++ priority_queue is a max-heap by default. You need greater<> as the third template argument to make it a min-heap. Alternatively, push negative distances — but greater<> is cleaner.

4. Unreachable Nodes

If a node is unreachable from the source, its distance stays at LLONG_MAX. Be careful with arithmetic on these — LLONG_MAX + w overflows. The if (d > dist[u]) continue guard implicitly protects against this since unreachable nodes never get pushed.

Key insight. Dijkstra processes each node at most once (after which it's finalized). Each edge is relaxed at most once. The PQ can hold at most \(E\) entries. Total time: \(O((V + E) \log E)\), which is \(O((V + E) \log V)\) since \(E \leq V^2\).

Path Reconstruction

Dijkstra finds distances. To recover the actual path, track predecessors:

vector<int> par(n + 1, -1);

// Inside relaxation:
if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
    par[v] = u;
    pq.push({dist[v], v});
}

// Reconstruct path to target:
vector<int> path;
for (int v = target; v != -1; v = par[v])
    path.push_back(v);
reverse(path.begin(), path.end());

If par[target] is still \(-1\) and target is not the source, no path exists.

Exercises

Modify the trace. Add an edge 3→5 (1) to the example graph. Re-run Dijkstra. Does the shortest path to node 5 change?
Bidirectional edges. The CSES problem has directed edges. If the graph were undirected, what changes in the code? (Just one line in the input loop.)
Multiple sources. How would you find the shortest distance from ANY of \(k\) source nodes to every other node? (Hint: push all sources into the PQ at distance 0.)

Problems

Problem	Link	Difficulty
CSES — Shortest Routes I	cses.fi/problemset/task/1671	Easy
LC 743 — Network Delay Time	leetcode.com/problems/network-delay-time	Medium
LC 1514 — Path with Maximum Probability	leetcode.com/problems/path-with-maximum-probability	Medium
LC 1631 — Path With Minimum Effort	leetcode.com/problems/path-with-minimum-effort	Medium
CSES — Flight Discount	cses.fi/problemset/task/1195	Medium