---
title: "Dijkstra's Algorithm"
summary: The greedy that works because distances only ever grow — with the proof, the four implementations, and the shapes of problem that are one Dijkstra away.
difficulty: core
tags: [shortest-path, greedy, heap]
time: (n + m) log n
space: n + m
prereq: [foundations/representation, structures/heap]
see: [shortest/bellman-ford, shortest/sparse-tricks]
demo: dijkstra
---

Given edge weights $w: E \to \mathbb{R}_{\ge 0}$ and a source $s$, compute $\operatorname{dist}(s, v)$ for every vertex $v$ — the length of the cheapest walk, where non-negative weights make "cheapest walk" and "cheapest path" the same number.
The algorithm is greedy, the proof is two lines of bookkeeping, and the *variants* (state augmentation) are what contests actually test.

## The algorithm in five lines of intent
1. Keep a tentative distance $d[v]$ for every vertex, initially $\infty$ except $d[s] = 0$.
2. Extract the unprocessed vertex $u$ with minimum $d[u]$.
3. $u$ is now **settled**: $d[u] = \operatorname{dist}(s,u)$.
4. **Relax** every edge $uv$: if $d[u] + w(u,v) < d[v]$, write the better value and push $(d[v], v)$.
5. Repeat.

```cpp dijkstra-real.cpp
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != d[u]) continue;          // stale entry: lazy deletion
        if (done[u]) continue;
        done[u] = 1;
        for (auto [v, w] : g[u]) if (d[u] + w < d[v]) {
            d[v] = d[u] + w;
            pq.emplace(d[v], v);
        }
    }
```

:::theorem title="Correctness"
If all weights are non-negative, then when $u$ is extracted with $d[u] \ne \infty$, $d[u] = \operatorname{dist}(s,u)$.
:::

:::proof
Induct on the extraction order. Invariant: $d[v] \ge \operatorname{dist}(s,v)$ always — true initially ($\infty$), and preserved because every update sets $d[v]$ to the length of an actual path ($s \leadsto u$ optimal, by hypothesis, plus the edge $uv$).
Now suppose $u$'s extraction value were *too big*: take a shortest path $\pi$ from $s$ to $u$; let $y$ be its first vertex not yet settled and $x$ its predecessor on $\pi$ (settled, since $s$ is settled and $u$ is not). When $x$ was settled, relaxation set $d[y] \le \operatorname{dist}(s,x) + w(x,y) = \operatorname{dist}(s,y)$. Since weights are non-negative, $\operatorname{dist}(s,y) \le \operatorname{dist}(s,u) < d[u]$. So $d[y] < d[u]$, and $y$ (unsettled) would have been extracted before $u$ — contradiction. ∎
:::

:::note title="Where non-negativity is used — exactly once"
The line $\operatorname{dist}(s,y) \le \operatorname{dist}(s,u)$. If an edge after $y$ on $\pi$ had negative weight, $u$ could be closer than $y$, and settling $u$ early would be wrong. This is why Bellman–Ford exists (@shortest/bellman-ford), and why "Dijkstra with a re-weighting fix" (Johnson potentials) is the honest way to handle negative weights that are known to be acyclic-safe.
:::

## The four implementations, honestly compared
| variant | push | pop | time | when |
|---|---|---|---|---|
| linear scan for min | $O(1)$ | $O(n)$ | $O(n^2)$ | dense: $m = \Theta(n^2)$, $n \le 5000$; no heap code, best constants |
| binary heap + lazy deletion | $O(\log)$ | $O(\log)$ | $O((n+m)\log n)$ | the default, 10 lines |
| `std::set` (decrease-key) | erase+insert | $O(\log n)$ | $O((n+m)\log n)$ | when you *need* real decrease-key (fewer stale entries) |
| pairing / Fibonacci heap | $O(1)$ | $O(\log n)$ | $O(m + n\log n)$ | theory, and $m \gg n$ |
| Dial / radix heap | — | — | $O(m + nC)$ / $O(m + n\log C)$ | small integer weights (@shortest/sparse-tricks) |

```cpp dijkstra-dense.cpp
vector<ll> d(n, INF); vector<char> used(n); d[s] = 0;
for (int it = 0; it < n; it++) {
    int u = -1;
    for (int i = 0; i < n; i++) if (!used[i] && (u == -1 || d[i] < d[u])) u = i;
    used[u] = 1;
    for (int v = 0; v < n; v) if (w[u][v] < INF) d[v] = min(d[v], d[u] + w[u][v]);
}
```
This $O(n^2)$ version beats the heap version for $n \le 2000$ on dense graphs and has no stale-entry subtlety — know both.

:::props title="The same code, seven different answers"
- **Reconstruct the path**: keep `par[v]` inside the relaxation; walk back from the target.
- **Number of shortest paths**: `if (d[u]+w == d[v]) ways[v] += ways[u];` — but process vertices in *settled order*, not relaxation order (push `(d[v], v)` and accumulate when popping, or topologically on the shortest-path DAG).
- **Second shortest path**: state = (vertex, used-or-not one "detour") → run Dijkstra on $2n$ states.
- **Dijkstra with a discount/coupon/special edge**: state = (vertex, coupon used) — the "layered graph" idiom (@shortest/sparse-tricks).
- **Bounded hops ($\le k$ edges)**: $\operatorname{dp}[\text{hops}][v]$ relaxations = $k$ Bellman-Ford rounds, or Dijkstra with hops in the state.
- **Multi-source**: push all sources with 0.
- **Negative-free all-pairs**: run it $n$ times, $O(nm + n^2 \log n)$ — better than Floyd for sparse graphs (@shortest/bellman-ford mention in sparse-tricks).
:::

:::demo id="dijkstra" caption="Every extraction, every relaxation and every stale duplicate on this 7-vertex network. Change the source and watch which vertices settle in a different order — but never a different distance."
:::

:::warning title="Four ways this breaks in a contest"
1. **Overflow.** $d[u] + w$ with $d[u] = \infty$ overflows `long long` if INF is `LLONG_MAX`. Use `INF = 4e18` and compare with `d[u] + w < d[v]` only after checking `d[u] < INF`.
2. **Zero-weight edges** are fine; **negative** ones are not — Dijkstra may return a too-small value for some vertices and the correct one for others, which is worse than crashing.
3. `greater<pair<ll,int>>` vs `less<>`: forgetting the comparator gives a max-heap and a wrong order (but sometimes still the right answer by luck — never ship that).
4. Marking `done[u]` at push time instead of pop time breaks the lazy-deletion scheme.
:::

:::problems
- [[CSES 1671]] Shortest Routes I | https://cses.fi/problemset/task/1671 | easy | straight Dijkstra
- [[CSES 1195]] Flight Discount | https://cses.fi/problemset/task/1195 | core | two-layer state
- [[CF 459E]] Pashmak and Graph | https://codeforces.com/problemset/problem/459/E | hard | edge classification
- [[CF 786B]] Legacy | https://codeforces.com/problemset/problem/786/B | hard | layered/auxiliary vertices
:::