Dijkstra
Single-source shortest paths with non-negative weights, in .
When
A graph with weights and the question "minimum cost from ". If all weights are equal, BFS is enough. If some are negative, you need Bellman–Ford.
The idea
BFS with a heap instead of a queue. Each time we take out the vertex with the smallest tentative distance. Because the weights are non-negative, no path through vertices that have not been taken out yet can be shorter. So the distance of this vertex is final.
The STL priority_queue has no decrease-key. Instead, we push the vertex again with the new distance and, when an old entry comes out, skip it: if (d > dist[u]) continue;. The heap can reach entries, but , so the complexity does not change.
The move that unlocks problems
State graph. In Flight Discount you can use a half-price coupon once. The state is the pair (city, have I used the coupon?), that is vertices. From you go to at cost and to at cost . Dijkstra runs unchanged.
In Investigation you want, besides the minimum cost, how many minimum routes there are. These are updated inside the relaxation: on a tie you add, on an improvement you replace.
Pitfalls
- Distances in
long long, "infinity" asLLONG_MAX. Do not add a weight to infinity. The code here never does, because it relaxes only from vertices that have left the heap. - Without the
continuefor stale entries the algorithm stays correct, but on a dense graph it becomes in the worst case.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Dijkstra with a binary heap: shortest paths from src, non-negative weights. O((n + m) log n).
// Stale heap entries (d > dist[u]) are skipped instead of decreased.
// Unreachable vertices keep LLONG_MAX.
vector<ll> dijkstra(const vector<vector<pair<int, ll>>>& adj, int src) {
int n = adj.size();
vector<ll> dist(n, LLONG_MAX);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) {
continue;
}
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Shortest Routes I · Graph Algorithms
- Flight Discount · Graph Algorithms
- Investigation · Graph Algorithms
More in the USACO Guide
- Shortest Paths with Non-Negative Edge Weights · usaco.guide/gold/shortest-paths
In English, with more problems per level.