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 stops can be strictly worse than reaching it for £200 with stops remaining — so "cheapest so far" is no longer sufficient to prune. Two fixes work: promote the state to (city, stops used), or use Bellman-Ford and relax all edges exactly k + 1 times, 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 one-line 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

# state: (cost so far, city, stops used)
heap = [(0, src, 0)]
best = {}                                   # (city, stops) -> 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:
        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))

The visited set is keyed on (city, stops), not on city alone. That single change restores the invariant: within a fixed stop 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 — but it needs a snapshot of the previous round's distances, or a single round can chain several edges and silently exceed the stop limit.

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. Two options:

• DFS/BFS over the graph, carrying the running product. Fine when you only need a valid rate, which is what the problem asks.
• Take logarithms. log(a × b) = log(a) + log(b), so a product path becomes a sum path and the usual machinery applies. This is exactly how arbitrage detection works — a negative-weight cycle after the log transform 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 — then undo the merges for anyone who did not actually learn it. 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 ordinary Dijkstra. 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 k layovers 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. Either (city, stops) Dijkstra, or Bellman-Ford relaxed k + 1 times over a snapshot of the previous round.
Pattern: constraint as a state dimension. Target: O(E·k log(V·k)) heap-based, or O(k·E) Bellman-Ford.

▶ Currency Conversion Rate

Convert between currencies through a chain of exchange rates. Carry the running product through a traversal, or log-transform to reduce it to additive shortest path.
Pattern: multiplicative path weights. Target: O(V + E) per query.

▶ Find All People With Secret

Determine who knows a secret after time-ordered meetings. Group meetings by timestamp, propagate within each group, and retract for anyone who did not learn it.
Pattern: time-ordered propagation with rollback. Target: O(m log m) for sorting plus near-linear union-find.

▶ The Maze II

Shortest rolling distance to a destination, where the ball slides until it hits a wall. Build neighbours as stopping points weighted by distance travelled, then run Dijkstra.
Pattern: graph construction, then standard Dijkstra. Target: O(mn log(mn)) time.

---

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 without the log transform, or to negative weights at all.
• Treating adjacent cells as neighbours in a rolling maze. Neighbours are stopping points; the distance rolled is the weight.
• Processing meetings one at a time in the secret problem. Simultaneous meetings interact and must be handled as a group.
• Forgetting to retract. Someone merged into a group that turned out not to know the secret must be reset, 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

1. Dijkstra's promise is conditional. It holds only when "cheapest so far" is sufficient to prune.
2. Put the constraint in the state. (node, budget) restores the invariant at the cost of a larger graph.
3. Bellman-Ford bounds path length structurally, which is often the shorter answer for stop limits — with a snapshot per round.
4. Logarithms turn products into sums, which is how multiplicative graphs rejoin the standard toolkit.
5. Sometimes the ordering is time, not distance, and grouping simultaneous events is what makes it correct.
6. Most of the work can be graph construction. Defining a neighbour correctly is the whole of the maze problem.
7. 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.