Weighted Graphs
What is this?
Dijkstra's algorithm rests on one promise: once a node is popped from the frontier, its distance is final. Nothing cheaper can arrive later, because every remaining path is already at least as expensive. That promise is what makes it fast, and it is also what breaks the moment a problem adds a constraint.
If reaching a city cheaply but with no fuel left is worse than reaching it expensively with fuel to spare, then "the node" is not the whole story. The fix is not a different algorithm, it is a bigger definition of state.
Fun fact: Cheapest Flights Within K Stops is the standard demonstration that Dijkstra's greedy invariant is conditional. Reaching a city for 100 using all your flights can be strictly worse than reaching it for 200 with flights to spare, so "cheapest so far" is no longer sufficient to prune. Two fixes work: promote the state to
(city, flights used), or use Bellman-Ford and relax all edges exactlyk + 1times (kstops means at mostk + 1flights), which bounds the path length by construction and is the shorter thing to write.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The core idea: when a constraint makes "cheapest so far" an insufficient reason to prune, put the constraint into the state. The algorithm does not change; the graph you are searching gets one dimension larger.
1. The extra dimension
import heapq
INF = float("inf")
# state: (cost so far, city, flights used); k stops allow k + 1 flights
heap = [(0, src, 0)]
best = {} # (city, flights) -> cheapest cost seen
while heap:
cost, city, stops = heapq.heappop(heap)
if city == dst:
return cost # first pop of dst is optimal
if stops > k: # a (k+1)-th flight was just used; no more allowed
continue
for nxt, price in adj[city]:
if best.get((nxt, stops + 1), INF) > cost + price:
best[(nxt, stops + 1)] = cost + price
heapq.heappush(heap, (cost + price, nxt, stops + 1))
return -1 # dst never reached within k + 1 flights
The visited map is keyed on (city, flights used), not on city alone. That single change restores the invariant: within a fixed flight count, cheaper really is better, so popping is safe again.
Bellman-Ford is the alternative and is often the better interview answer for this problem, because relaxing all edges k + 1 times bounds path length structurally. It needs a snapshot of the previous round's distances, or a single round can chain several edges and silently exceed the stop limit. It costs O(k * E) time and O(n) space.
2. When costs multiply
Currency Conversion Rate asks for a path product rather than a sum: converting A→B→C multiplies the two rates. Dijkstra's correctness argument depends on edge weights being non-negative additive costs, so it does not transfer directly. If the rate table is consistent, every path between two currencies gives the same product, so there is nothing to minimise. Two options:
- BFS over the graph, carrying the running product. This is the lesson's first approach:
O(V + E)per query, and it answers "is there a path, and what is the product". - Weighted union-find for many queries: each currency stores its ratio to its root, so a query is a find on each side and one division.
For best-rate or arbitrage variants you can take logarithms: log(a × b) = log(a) + log(b), so a product path becomes a sum path. The weights can then be negative, so use Bellman-Ford rather than Dijkstra; a negative cycle is a profitable loop.
3. Time as the ordering
Find All People With Secret is not really a shortest-path problem: meetings happen at timestamps, and the secret can only pass at a meeting if a participant already knows it at that time. Process meetings grouped by timestamp, and within each group propagate knowledge among that group's participants. The lesson does this two ways: a BFS per timestamp group starting from the people who already know, or a union-find that is reset for anyone in the group who did not end up connected to a secret holder. Ordering by time is the whole algorithm; the graph structure is secondary.
4. When an edge is a slide
In The Maze II a ball rolls until it hits a wall, so the neighbours of a cell are not the four adjacent cells but the stopping points in each direction, and the edge weight is the distance travelled to get there. Once the graph is defined that way, it is a shortest-path problem. BFS by number of rolls is wrong, because it minimises rolls rather than cells travelled. The lesson shows a correct but slower re-enqueue version (relax a stop again whenever a shorter distance arrives) and then Dijkstra over stopping points. Almost all the difficulty is in constructing the right graph.
5. Where you'll actually meet this
- Flight and route search. Cheapest fare with at most
klayovers is the literal problem, constraints and all. - Currency arbitrage. Log-transformed exchange graphs with negative-cycle detection is how trading systems find risk-free loops.
- Network routing with hop limits. TTL-bounded shortest paths need the same
(node, hops)state. - Contact tracing. Time-ordered propagation with retraction is Find All People With Secret under a different name.
- Game physics and puzzles. Sliding-block movement where the piece continues until obstructed.
6. Problems in this chapter
Cheapest Flights Within K Stops
Cheapest route using at most k stops (k + 1 flights). Either Bellman-Ford relaxed k + 1 times over a snapshot of the previous round, or Dijkstra on (city, flights used).
Pattern: constraint as a state dimension. Target: O(k·E) time and O(n) space for Bellman-Ford; O(k·E·log(k·E)) for the heap version.
Currency Conversion Rate
Convert between currencies through a chain of exchange rates. BFS carrying a running product, or weighted union-find when there are many queries.
Pattern: multiplicative path weights. Target: O(V + E) per query with BFS; O(log V) amortized per query after an O(E log V) build with union-find.
Find All People With Secret
Determine who knows a secret after time-ordered meetings. Group meetings by timestamp, then BFS within each group from the people who know, or use union-find and reset the people who did not learn it.
Pattern: time-ordered propagation with rollback. Target: O(M log M) time for sorting plus near-linear work, O(n + M) space.
The Maze II
Shortest rolling distance to a destination, where the ball slides until it hits a wall. BFS by rolls is wrong. Re-enqueue on improvement is correct but slow; Dijkstra over stopping points, weighted by distance travelled, is the answer.
Pattern: graph construction, then standard Dijkstra. Target: O(mn(m + n) + mn log(mn)) time, O(mn) space.
7. Common pitfalls
- Keying the visited set on the node alone when a budget exists. This is the bug in constrained shortest paths.
- Relaxing in place in Bellman-Ford. Without a snapshot of the previous round's distances, one round can chain multiple edges and break the stop limit.
- Applying Dijkstra to multiplicative weights directly, or to negative weights (which is what log-transformed rates produce).
- Treating adjacent cells as neighbours in a rolling maze. Neighbours are stopping points; the distance rolled is the weight.
- Running BFS by number of rolls in The Maze II. It minimises rolls, not cells travelled.
- Processing meetings one at a time in the secret problem. Simultaneous meetings interact and must be handled as a group.
- Forgetting to reset. Someone merged into a group that turned out not to know the secret must be reset in the union-find, or the answer over-reports.
- Missing the early exit. With plain Dijkstra the first pop of the destination is final; with the extra dimension it is still final, but only because the state includes the budget.
8. Key takeaways
- Dijkstra's promise is conditional. It holds only when "cheapest so far" is sufficient to prune.
- Put the constraint in the state.
(node, budget)restores the invariant at the cost of a larger graph. - Bellman-Ford bounds path length structurally, which is often the shorter answer for stop limits, with a snapshot per round.
- Multiplicative paths need a traversal that carries a product, or weighted union-find for many queries. Logarithms turn them into sums, but the weights go negative.
- Sometimes the ordering is time, not distance, and grouping simultaneous events is what makes it correct.
- Most of the work can be graph construction. Defining a neighbour correctly is the whole of the maze problem.
- Why interviewers love it: they can watch you reach for Dijkstra, hit the constraint, and either patch it thoughtfully or not notice the invariant broke at all.
Order: Cheapest Flights Within K Stops → Currency Conversion Rate → Find All People With Secret → The Maze II.