Breadth-first search finds shortest paths when every edge has the same length. As soon as edges have different weights, such as road lengths or travel times, BFS gives wrong answers. Dijkstra's algorithm is the standard fix for graphs whose edge weights are non-negative.
The problem
There are n cities and m one-way flights, each with a cost. Find the cheapest cost from city 1 to every city. This is CSES 1671 – Shortest Routes I, with n up to 105 and m up to 2 × 105.
The idea
Keep a tentative distance for every node, starting at 0 for the source and infinity for the rest. Then repeat:
- Take the unfinished node u with the smallest tentative distance. That distance is now final.
- For every edge u → v with weight w, check whether going through u is cheaper: if dist[u] + w < dist[v], update dist[v]. This is called relaxing the edge.
Why the smallest node is final
Suppose u has the smallest tentative distance d. Any other route to u would have to leave the set of finished nodes through some unfinished node, whose distance is already at least d. Adding more edges can only make that route longer, because weights are non-negative. So no route can beat d.
That argument is exactly where negative edges break things: a negative edge could make a longer-looking path cheaper later. With negative weights, use Bellman–Ford instead.
Finding the minimum quickly
Scanning all nodes for the minimum each time is O(n2). A min-heap (priority_queue with greater<>) gives the smallest entry in O(log n). Whenever we improve a distance, we push the new (distance, node) pair.
A node can end up in the heap several times with older, larger distances. Instead of deleting those, we simply skip any entry whose distance does not match the current dist[u]. These are called stale entries.
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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 w;
cin >> a >> b >> w;
adj[a].push_back({b, w}); // directed edge a -> b with weight w
}
const long long INF = LLONG_MAX;
vector<long long> dist(n + 1, INF);
// min-heap of (distance, node)
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue; // stale entry, skip it
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] << (i == n ? '\n' : ' ');
return 0;
}Example
3 4
1 2 6
1 3 2
3 2 3
1 3 4The direct flight 1 → 2 costs 6, but 1 → 3 → 2 costs 2 + 3 = 5. Output: 0 5 2.
Step by step: pop city 1 (distance 0) and relax its edges, so city 2 gets 6 and city 3 gets 2. Pop city 3 (distance 2) and relax 3 → 2, improving city 2 to 5. Pop city 2 (distance 5). The old entry (6, city 2) is popped later and skipped as stale.
Complexity
Each edge can push at most one entry, so the heap holds O(m) entries. Total time is O((n + m) log m), and memory is O(n + m).
Common mistakes
- Using a max-heap. C++'s
priority_queuereturns the largest element by default. Usegreater<>, or push negative distances. - Forgetting the stale check. Without
if (d != dist[u]) continue;the answer is still correct, but on some graphs the algorithm becomes much slower. - Using
intdistances. A path of 105 edges with weight 109 each sums to 1014. Uselong long. - Undirected graphs. If roads go both ways, add each edge in both directions.
Practice problems
- CSES 1671 – Shortest Routes I: the problem in this post.
- Codeforces 20C – Dijkstra?: also print the path itself, by storing each node's parent when you relax an edge.
If BFS is still new to you, start with the BFS deep dive. Dijkstra is the same idea with a priority queue in place of a plain queue.
