Dijkstra
Single-source shortest paths in non-negative weighted graphs with a min-heap and lazy deletions.
Dijkstra
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Dijkstra's algorithm is the shortest-path routine for graphs with nonnegative edge weights. It grows the known region outward from a source, always finalizing the not-yet-finalized vertex with the smallest tentative distance.
This is one of the most reused graph patterns in contests. Once the priority-queue invariant is clear, the code is short and reliable.
When to Use It
Use it when:
all edge weights are nonnegative,
you need distances from one source to many vertices,
the graph is sparse enough for an adjacency list and heap to be natural,
BFS is too weak because weights are not all equal.
If the edges are only \(0\) and \(1\), 0-1 BFS is often better. If negative edges exist, the key greedy invariant breaks and Bellman-Ford or something stronger is needed.
Core Idea
Maintain tentative distances \(\texttt{dist[v]}\). Initially only the source has distance \(0\); everyone else is infinity.
The heap stores candidates \((d, v)\). Each step extracts the smallest candidate. If it matches the current stored distance, then \(v\) is finalized and all outgoing edges are relaxed.
Relaxing \((v, to, w)\) means checking whether going through \(v\) improves \(\texttt{dist[to]}\): \[ \texttt{dist[to]} > \texttt{dist[v]} + w. \]
Key Insight
The priority queue is not just a speed trick. It enforces the main correctness invariant: \textbf{when a fresh state \((d, v)\) leaves the heap, \(d\) is already the true shortest distance to \(v\)}.
That is exactly why nonnegative edges matter. If an unseen path could later subtract weight, then the ``smallest tentative distance is safe to finalize'' rule would no longer hold.
Operations / Main Technique
The ordinary sparse-graph version uses:
an adjacency list,
a min-heap,
one distance array,
optional parent pointers for restoring a shortest path.
Stale entries.
I almost always use the lazy heap version: push improved states freely, and when popping, skip the state if it no longer matches \(\texttt{dist[v]}\). That avoids a more complicated decrease-key structure.
Worked example.
If the heap contains both \((9, x)\) and later \((5, x)\), then the first one is stale by the time it is popped. Skipping it is not optional bookkeeping. It is how the lazy version stays correct and simple.
Correctness Intuition
Assume the heap pops a fresh state \((d, v)\). Suppose for contradiction there were a strictly shorter path to \(v\). Walk along that path from the source until you reach the first not-yet-finalized vertex. Its predecessor on the path was already finalized earlier, so the relaxation from that predecessor would have inserted a candidate no larger than the true path length.
That candidate should have been popped before \((d, v)\), contradicting the choice of \(v\) as the smallest fresh tentative distance. Therefore \(d\) is final.
Complexity Analysis
heap-based Dijkstra on a sparse graph: \(O((n + m)\log n)\),
memory: \(O(n + m)\).
The heap receives at most one new state per successful relaxation, and each push/pop costs a logarithm.
Implementation
The reference code keeps:
adjacency lists of \((to, weight)\),
a
priority_queuewithgreater<...>,long longdistances,parent restoration for one concrete shortest path.
That is the version I trust most under contest pressure. Multi-source Dijkstra is just the same code with several initial zero-distance pushes.
Common Pitfalls
Running Dijkstra on graphs with negative edges.
Forgetting to skip stale heap entries.
Using
intwhen path lengths needlong long.Choosing infinity too small and overflowing during relaxation.
Missing simpler special cases such as BFS or 0-1 BFS.
Variants / Extensions
multi-source Dijkstra,
Dijkstra on state graphs instead of ordinary vertices,
counting shortest paths while relaxing,
Dijkstra with potentials inside Johnson-style reweighting or min-cost-flow subroutines.
In CP, ``run Dijkstra on a product state'' is often more useful than the textbook graph-only framing.
Practice Problems
CSES:
Shortest Routes I.CSES:
Flight Routes.Weighted shortest-path problems where the graph is built from problem states rather than explicit roads.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Dijkstra {
static constexpr long long INF = (1LL << 62);
int n;
vector<vector<pair<int, int>>> adj;
Dijkstra() : n(0) {}
explicit Dijkstra(int n) { init(n); }
void init(int n_) {
n = n_;
adj.assign(n, {});
}
void add_edge(int u, int v, int w, bool undirected = false) {
adj[u].push_back({v, w});
if (undirected) adj[v].push_back({u, w});
}
pair<vector<long long>, vector<int>> shortest_paths(int source) const {
vector<long long> dist(n, INF);
vector<int> parent(n, -1);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du != dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (dist[v] > du + w) {
dist[v] = du + w;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
return {dist, parent};
}
vector<int> restore_path(int source, int target, const vector<int>& parent) const {
vector<int> path;
for (int v = target; v != -1; v = parent[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
if (path.empty() || path[0] != source) return {};
return path;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.