Canonical Deep-Dive: Cheapest Flights Within K Stops

Problem: Cheapest Flights Within K Stops (https://leetcode.com/problems/cheapest-flights-within-k-stops/) The lesson: the node alone is not the state. When a constraint rides on the path, you expand the state to carry it.

This is a guided walk-through, not an answer key. It explains how to think about the state of a constrained shortest-path problem, shows you the relaxation as a relation and the round structure in words, and contrasts two correct algorithms. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given n cities labeled 0 to n - 1, a list of flights where each entry [u, v, w] is a one-way flight from u to v costing w, a source src, a destination dst, and an integer k. Return the cheapest total price to get from src to dst using at most k stops (a stop is an intermediate city, so the path may use at most k + 1 flights). If there is no such route, return -1.

Anchor on the official examples before reading further:

n = 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1. Answer 700. The route 0 -> 1 -> 3 costs 100 + 600 = 700 and uses one stop (city 1). The cheaper-looking 0 -> 1 -> 2 -> 3 costs 100 + 100 + 200 = 400, but it uses two stops, which exceeds k = 1, so it is not allowed.
n = 3, flights [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1. Answer 200. The route 0 -> 1 -> 2 costs 200 and uses one stop, within budget.
Same graph, k = 0. Answer 500. With zero stops you may only take a single direct flight, so 0 -> 2 for 500 is the only legal route.

That second-and-third pair is the whole lesson in miniature: the cheapest way to reach city 2 is 200, but only when you are allowed a stop. Tighten k to 0 and the answer changes to 500, even though the graph did not. The cost to reach a city is not a single number; it depends on how many stops you have spent getting there.

Why a plain Dijkstra is a trap here

Your first instinct, fresh off the recognition cue, is correct that this is a weighted shortest-path problem, and the weights are non-negative, so Dijkstra should fit. Reach for the usual machinery: a min-heap of (cost, node), pop the closest unsettled node, mark it visited, relax its neighbors, and the first time you pop dst you have the answer.

That machinery returns the wrong answer, and the first example shows exactly why. Plain Dijkstra finalizes city 1 cheaply, then finalizes city 2 (via 0 -> 1 -> 2 for 200), then reaches city 3 through city 2 for 400 and reports it. But that route spent two stops; the constraint allowed only one. Dijkstra optimized the one number it knows about, total cost, and was blind to the stop count riding alongside it.

The deeper failure is the visited set. Dijkstra’s correctness depends on finalizing each node once: the first pop is final. Here that is false. Reaching city 2 by the cheapest route also commits you to a stop count, and a more expensive arrival at city 2 that used fewer stops might be the only one that can still legally reach dst within budget. Marking city 2 “done” on its cheapest arrival throws that alternative away. The number you optimize and the constraint you must respect have come apart, and a node-keyed visited set cannot tell them apart.

The fix: expand the state

The repair is the heavy concept of the week. Stop asking “what is the cheapest cost to reach this city” and start asking “what is the cheapest cost to reach this city having used this many stops”. The state is the pair:

(node, stops_used)

Two arrivals at the same city with different stop counts are different states. City 2 reached with one stop and city 2 reached with two stops are tracked separately, because they have different futures: one can still afford another hop under a tight budget, the other cannot. Once the state carries the constraint, a standard shortest-path algorithm works again, because redundancy is now judged on the full pair, not the bare node.

The brute-force baseline

Before optimizing, have a baseline. The recursive brute force: define “cheapest cost from node to dst using at most s more stops”. To solve it, try every outgoing flight node -> v of cost w, and recursively solve from v with s - 1 stops remaining; the answer is w plus the best of those subresults. The base cases are “if node == dst, cost 0” and “if you are out of stops and not at dst, this path is impossible”.

Time: exponential. The same (node, stops remaining) subproblem is recomputed through many different flight sequences.
Space: O(k) for the recursion stack depth.

Write it and watch the repetition. That repetition over (node, stops) subproblems is the signal: the same expanded state is being recomputed, so the fix is to compute each expanded state once. Memoizing this recursion on (node, stops) is one correct solution; below is the iterative form that fits this problem most cleanly.

Bellman-Ford, where the round index is the stops dimension

Here is the clean fit. Recall Bellman-Ford: relax every edge, and repeat; after i rounds, every shortest path that uses at most i edges is correct. Now read the constraint again. “At most k stops” means “at most k + 1 flights”, which means “at most k + 1 edges”. The thing Bellman-Ford bounds by its round count, the number of edges on the path, is exactly the constraint this problem imposes. The algorithm’s natural dial and the problem’s constraint are the same dial. That is why Bellman-Ford is the clean tool here and not a compromise.

So you run exactly k + 1 rounds of edge relaxation. The state expansion is implicit in the rounds: “the best cost to a city after at most i rounds” is precisely “the best cost to that city using at most i flights”. Let dist hold the best known cost to each city. The relaxation, as a relation, is:

new cost to v  =  min( cost to u so far  +  w )   over every flight (u, v, w)

with one rule that is the entire correctness of the bounded version:

In each round, you must relax using the costs as they stood at the end of the previous round, not costs updated earlier in the same round.

Concretely, at the start of a round you snapshot the current dist, and every relaxation in that round reads from the snapshot while writing into the fresh copy. Why this matters: if you relaxed in place, a flight improved earlier in the same round could feed a second flight later in the same round, and a single round would chain two (or more) flights together. That would let one round add several edges to a path and quietly overspend your stop budget, returning a too-cheap, illegal answer. The per-round snapshot forces each round to extend every path by at most one edge, so after k + 1 rounds no path has more than k + 1 edges, exactly the budget.

The five beats, mapped onto this problem:

1. State. dist[v] is the cheapest known cost to reach city v using at most the number of flights allowed by the rounds run so far. The stop dimension lives in the round index rather than in the array key, which is what makes this form so compact.

2. Transition (the relaxation). new_dist[v] = min(new_dist[v], dist[u] + w) for every flight (u, v, w), reading dist from the previous round’s snapshot.

3. Base case. dist[src] = 0; every other city starts at float('inf') (“not yet reached”), so the first real cost to arrive replaces it.

4. Order of computation. Run k + 1 rounds. Each round, work from a snapshot of the previous round’s dist so a round can chain at most one new flight onto any path.

5. Answer extraction. After the rounds, the answer is dist[dst], with the impossibility correction: if it is still float('inf'), return -1.

Trace the first example to feel it. Round 1 (paths of at most one flight from city 0): city 1 becomes 100, city 2 stays infinite (no direct 0 -> 2), city 3 stays infinite. Round 2 (at most two flights, so at most one stop): from city 1 you reach city 3 at 100 + 600 = 700, and city 2 at 100 + 100 = 200. Two rounds is k + 1 = 2, so you stop. dist[3] is 700. The route through city 2 to city 3 would need a third round (three flights, two stops), which the budget forbids, so it never enters the answer. That is the constraint enforcing itself through the round count.

The other correct way: Dijkstra over the expanded state

Bellman-Ford is the clean fit, but it is worth seeing that the state-expansion idea also rescues Dijkstra, because the contrast sharpens what went wrong with the plain version. Make the heap entries carry the full state: (cost, node, stops_used). Pop the cheapest, and if it is dst, return its cost. Otherwise, if it still has stop budget left (stops_used <= k), push (cost + w, v, stops_used + 1) for each neighbor.

The one rule that makes it correct: do not keep a global node-keyed visited set. A node can be legitimately reached many times with different stop counts, and you must not finalize it on the first arrival. At most, track the best cost seen per expanded state (node, stops_used) and skip an entry only when you have already reached that exact pair more cheaply. The heap still pops in increasing cost order, so the first time you pop dst at any legal stop count, that cost is optimal among legal routes.

Two ways to read the same fix: Bellman-Ford folds the stop dimension into the round index; Dijkstra-with-state folds it into the heap entry and the per-state bookkeeping. Both abandon the assumption that a node is finalized once. That abandoned assumption is the whole lesson.

Exact complexity

For the Bellman-Ford form, with E = len(flights):

Time: O(k * E). You run k + 1 rounds, and each round relaxes all E flights once. There is no log factor, because there is no heap; it is a flat sweep over the edges, repeated a bounded number of times.
Space: O(n). One dist array over the n cities, plus the per-round snapshot, which is another array of the same size. No heap, no adjacency list required (you can iterate the raw flights list each round).

For the Dijkstra-over-state form, the bound is larger: there are up to O(n * k) distinct states and each can generate heap activity, giving roughly O(E * k * log(n * k)) time and O(n * k) space for the state bookkeeping. On this problem Bellman-Ford is both simpler to reason about and lighter, which is why it is the form to learn first.

Your work this week

Implement Cheapest Flights yourself, the Bellman-Ford way, in your own work repo (for example cheapest-flights.py). Initialize the dist array with float('inf') and dist[src] = 0, run k + 1 rounds, snapshot dist at the start of each round and relax from the snapshot, then extract dist[dst] with the -1 correction. Do not copy a solution; build it from the five beats above.
Then write the Dijkstra-over-expanded-state version: a heap of (cost, node, stops_used), no global node visited set, push neighbors only while stop budget remains. Confirm both give the same answers on the three official examples, and convince yourself they are the same idea (state expansion) with different bookkeeping.
Run both against the provided examples in practice/-style local tests, then submit to LeetCode’s judge. Test the edge cases yourself: k = 0 (only direct flights are legal, the third example), a dst that is genuinely unreachable within budget (answer -1), and a graph where the cheapest unconstrained path uses too many stops so the constrained answer is strictly larger (the first example).
Commit with a five-question debrief in the message. In answer 1, name the pattern as state expansion; in answer 3, state the exact complexity above (Bellman-Ford O(k * E) time, O(n) space) and why the per-round snapshot is what keeps a round from spending more than one edge of the budget.

When you can explain, from memory and with no AI open, why the node alone is not the state, why a plain Dijkstra with a node visited set returns a wrong answer on the first example, and why Bellman-Ford’s round count is the natural home for the stop budget, you own this problem. That explanation is exactly what an interviewer will ask for, and the state-expansion move is one you will reuse whenever a constraint rides on a path.