Shortest Paths (Weighted) Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide
When edges have weights, plain BFS is not enough. Dijkstra always expands the closest unfinished node next.
3 sub-patterns · 6 questions
What is this pattern?
When edges have different costs (times, prices, effort), the path with the fewest edges is not always the cheapest, so plain BFS stops working. Three algorithms cover almost every question, and the choice depends on the graph:
Dijkstra (non-negative weights, one source): keep a min-heap of (distance, node). Pop the closest node not settled yet; its distance is now final, because any other route would have to leave through a node that is at least as far. Then relax its edges: if dist[u] + w < dist[v], a cheaper way to v was found. O((V + E) log V).
Bellman-Ford (a limit on the number of edges, or negative weights): relax every edge in rounds. After round i, every route that uses at most i edges is known. Copying the array each round keeps the limit exact. O(K · E).
Floyd–Warshall (every pair, small n): for each node k, try it as a middle stop for every pair: d[i][j] = min(d[i][j], d[i][k] + d[k][j]). O(n³).
Water poured at the source spreading through pipes of different lengths. It reaches the nearest junction first, and once water is at a junction, no later trickle can arrive there sooner: that junction's time is final. Dijkstra simply follows the water front, always taking the junction the water reaches next. Bellman-Ford is checking every pipe again and again, each pass allowing one more pipe in the route.
See it move
Purple = popped now, green = settled, blue edge = shorter path found, orange edge = no gain. Heap cells are dist:node, smallest on the left.
n = 6, src = 0, edges (u→v, w): 0→1 4, 0→2 1, 2→1 2, 1→3 1, 2→3 5, 3→4 3, 2→4 8, 4→5 1, 3→5 6, 3→2 1step 1/12Every distance starts at ∞ except the source. The min-heap holds (distance, node) pairs, smallest first. Purple = the node popped now, green = settled (final), blue edge = an improvement, orange edge = no improvement.
Each round allows one more edge. Green = cost improved this round, blue edge = the edge that improved it, gold = the answer route.
n = 5, src = 0, dst = 4, k = 2 edges, flights: 0→1 1, 1→2 1, 2→4 1, 0→3 5, 3→4 1, 0→4 9step 1/4- round
- 0 (no edges yet)
- max edges
- 2
Find the cheapest route from 0 to 4 using at most 2 edges. With 0 edges only node 0 is reachable (cost 0). Each round lets every route use one more edge.
How do I recognise it?
Weighted edges and "minimum cost / time / distance" from one start.
"Time for a signal to reach all nodes" → Dijkstra, answer = the largest final distance.
A path score that isn't a sum: the maximum step on the path (effort), a product of probabilities → Dijkstra with a different combine rule.
"At most K stops / K edges" → Bellman-Ford with K + 1 rounds (or BFS over (node, stops)).
"For every city, how many others are within distance T" or any all-pairs question with n ≤ ~100–400 → Floyd–Warshall.
Negative edge weights → not Dijkstra; Bellman-Ford (and a V-th round that still improves means a negative cycle).
Looks like Shortest Paths (Weighted), but isn't
With equal weights BFS already reaches nodes in order of distance, with a plain queue in O(V + E). A heap only adds a log factor.
That is a minimum spanning tree: the total cost of a set of edges that connects everyone, not the cost of a route between two nodes. The two answers differ.
On a DAG, processing nodes in topological order computes any path value in O(V + E), including the longest path, which Dijkstra can't do.
How would I discover it from scratch?
Don't memorise “use shortest paths (weighted)”. Ask these questions in order — the pattern falls out.
BFS finishes a node the first time it is reached, which is the route with the fewest edges. With 0 → 1 costing 4 and 0 → 2 → 1 costing 1 + 2 = 3, BFS sets node 1 to 4 and never looks again. The cheaper route uses more edges.
Sub-patterns
Same core idea, different rule for “valid”. Learn them in this order.
Dijkstra
4 questionsCheapest route from one source when every edge cost is ≥ 0, including scores built with max or multiplication.
Bellman-Ford / limited stops
1 questionsCheapest route with a limit on how many edges it may use (or with negative weights).
All pairs (Floyd–Warshall)
1 questionsDistances between every pair of nodes in a small graph.
Don't mix these up
All edges cost the same (or the grid has no weights) → BFS. Different costs → Dijkstra. Dijkstra on equal weights works but is slower.
Dijkstra needs non-negative weights and no limit on the number of edges. A stop limit or a negative weight → Bellman-Ford.
Shortest path minimises one route from a source. MST minimises the total of a set of edges connecting everyone. On a triangle with edges 1, 1, 1.5 the MST drops the 1.5 edge, but the shortest route between its two ends is that 1.5 edge.
In Dijkstra a node's distance is final only when it is popped (BFS can mark on push because every edge costs 1). A later, cheaper route may still lower a node that is only sitting in the heap.
Code templates (C++)
Dijkstra with a min-heap and lazy deletion
Push (dist, node); on pop skip entries with d > dist[u]; relax with d + w < dist[v]. For effort use max(d, w); for probability flip to a max-heap and multiply.
// Dijkstra: always settle the closest unsettled node; its distance can't improve later.
// Works when every edge weight is >= 0.
vector<long long> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int src) { // adj[u] = {v, w}
const long long INF = LLONG_MAX;
vector<long long> dist(n, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq; // {dist, node}, min first
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // stale entry: u was settled with a smaller d
for (auto [v, w] : adj[u])
if (d + w < dist[v]) { // relax: a shorter way to v through u
dist[v] = d + w;
pq.push({dist[v], v});
}
}
return dist; // INF = unreachable
}Bellman-Ford with an edge limit
Run maxEdges rounds; each round reads dist and writes a copy, so a route can't gain two edges in one round. K stops = K + 1 edges.
// Bellman-Ford with at most k edges: round i finds every shortest path that uses <= i edges.
// Cheapest Flights Within K Stops = at most k + 1 edges.
int cheapestWithinEdges(int n, const vector<vector<int>>& edges, int src, int dst, int maxEdges) { // edges {u, v, w}
const int INF = INT_MAX;
vector<int> dist(n, INF);
dist[src] = 0;
for (int round = 0; round < maxEdges; round++) {
vector<int> next = dist; // copy: this round may only extend LAST round's paths
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (dist[u] != INF && dist[u] + w < next[v]) next[v] = dist[u] + w;
}
dist = next;
}
return dist[dst] == INF ? -1 : dist[dst];
}Floyd–Warshall: all pairs
Fill d with the direct edges (0 on the diagonal), then the k / i / j loops. Use a large-but-safe INF so INF + INF doesn't overflow.
// Floyd-Warshall: shortest path between every pair. After the k-loop finishes for k,
// d[i][j] is the best path whose middle nodes are all among 0..k.
vector<vector<long long>> allPairs(int n, const vector<vector<int>>& edges) { // undirected {u, v, w}
const long long INF = LLONG_MAX / 4; // /4 so INF + INF can't overflow
vector<vector<long long>> d(n, vector<long long>(n, INF));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (auto& e : edges) {
d[e[0]][e[1]] = min<long long>(d[e[0]][e[1]], e[2]);
d[e[1]][e[0]] = min<long long>(d[e[1]][e[0]], e[2]);
}
for (int k = 0; k < n; k++) // k MUST be the outer loop
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
return d;
}