Find the cheapest route from src to dst using at most k stops — that is, at most k + 1 flights. Return -1 if there is none.
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]src = 0, dst = 3, k = 1→ 700 (0 → 1 → 3, one stop)
In plain English, you want to fly from a starting city to a destination city as cheaply as possible. But there's a catch: you get airsick easily, so you absolutely refuse to take a route with more than k layovers (meaning k stops in the middle, or k+1 total flight legs). Find the cheapest route satisfying this condition. If none exists, return -1.
The route 0 → 1 → 2 → 3 costs only 500, but it uses two stops and is not allowed.
Imagine a travel agent looking for tickets. The agent says, "Good news! I got you to Chicago for just $50!" You say, "Great, from Chicago we can go to New York." The agent replies, "Ah, sorry, the $50 ticket took 8 layovers, and you said max 2 layovers. We can't go any further." You ask, "Well, did you see any slightly more expensive flights to Chicago that only had 1 layover?" The agent says, "I stopped looking the moment I found the $50 one!" That travel agent is Dijkstra. Dijkstra only cares about finding the absolute cheapest path to a node and immediately stops searching for other paths to that node. When you introduce a secondary constraint (like max layovers), Dijkstra's single-minded greediness breaks.
In the example, Dijkstra reaches node 2 cheaply via 0 → 1 → 2 for 200, then finalises it. But that route has already used two flights, so continuing to 3 needs a third and exceeds the limit. Meanwhile node 1 at cost 100 with one flight used is the route that actually works.
The lesson generalises: Dijkstra's finalisation is only valid when cost is the only thing that matters. Add a second constraint — hop count, fuel, time window — and a node's "best" state is no longer a single number, so a single finalised distance is not enough.
Two ways out.
Solution 1 — Bellman-Ford, and it fits perfectly
Bellman-Ford relaxes every edge, repeatedly. After i rounds, it knows the cheapest route using at most i edges.
That is exactly the constraint here. Run it k + 1 times and you have the cheapest route using at most k + 1 flights. The hop limit, which broke Dijkstra, is the very thing Bellman-Ford counts.
python
class Solution: def findCheapestPrice(self, n, flights, src, dst, k) -> int: INF = float('inf') # (1) cost = [INF] * n # (2) cost[src] = 0 # (3) for _ in range(k + 1): # (4) at most k+1 flights snapshot = cost[:] # (5) ← the critical line for u, v, w in flights: # (6) if snapshot[u] + w < cost[v]: # (7) cost[v] = snapshot[u] + w return cost[dst] if cost[dst] != INF else -1 # (8)
ts
function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number { const INF = Infinity; // (1) let cost = new Array(n).fill(INF); // (2) cost[src] = 0; // (3) for (let round = 0; round <= k; round++) { // (4) const snapshot = [...cost]; // (5) for (const [u, v, w] of flights) { // (6) if (snapshot[u] + w < cost[v]) cost[v] = snapshot[u] + w; // (7) } } return cost[dst] === INF ? -1 : cost[dst]; // (8)}
snapshot = cost[:] is the line the whole solution depends on.
Without it, a single round could chain several flights: relaxing 0 → 1 updates cost[1], and then relaxing 1 → 2 in the same round uses that fresh value, so two flights were taken in one round. The hop count becomes meaningless.
Copying the array first means every relaxation in a round reads the state from the end of the previous round, so exactly one flight is added per round. That is the difference between "at most i edges" and "any number of edges", and it is why standard Bellman-Ford — which does not snapshot — cannot answer this question directly.
O(k \times E) time, O(n) space. Short, and easy to defend.
This is the Bellman-Ford algorithm, limited to k + 1 rounds. After round r, cost[v] holds the cheapest price to reach v using at most r flights.
(1) Infinity stands for "not reachable yet".
(2) Every city starts unreachable,
(3) except the starting city, which costs nothing to be at.
(4) k stops means at most k + 1 flights, so run exactly k + 1 rounds.
(5) Copy the prices from the end of the previous round. This is the line that makes the stop limit work. Inside one round, every update must use prices from before the round. Otherwise a city updated early in this round could pass its new price on to another city in the same round, which would quietly use two flights in one round, and break the limit.
(6) Try every flight.
(7) If flying from u to v is cheaper than the best known price for v, using u's price from the snapshot, take it.
(8) The cheapest price to the destination, or −1 if it was never reached within k + 1 flights.
Walk outward one flight at a time, keeping the cheapest known cost to each node.
python
from collections import dequedef findCheapestPrice(self, n, flights, src, dst, k): adj = defaultdict(list) for u, v, w in flights: adj[u].append((v, w)) best = [float('inf')] * n best[src] = 0 queue = deque([(src, 0)]) stops = 0 while queue and stops <= k: for _ in range(len(queue)): # one level = one flight node, cost = queue.popleft() for nei, w in adj[node]: if cost + w < best[nei]: # only continue if we improved best[nei] = cost + w queue.append((nei, cost + w)) stops += 1 return best[dst] if best[dst] != float('inf') else -1
The level structure counts the flights, and pruning on cost + w < best[nei] stops the queue exploding. It is the same shape as every level-order BFS in this book.
Dijkstra can be rescued by changing what a "node" means. Make the state (node, flights used) rather than just node, and track the best cost for each combination.
python
heap = [(0, src, 0)] # (cost, node, flights used)
Now finalising is safe again, because two routes to the same airport with different flight counts are genuinely different states.
O(E \cdot k \log(V \cdot k)) — more code and more memory than Bellman-Ford. But the idea behind it is the important one:
When a second constraint breaks a graph algorithm, put the constraint into the state.
That move fixes fuel limits, time windows, "at most two refuels", and a large family of DP-on-graph problems. It is the same idea as adding a dimension to a DP table in 4.24.
Bellman-Ford. It is eight lines, the hop limit is native to it, and the snapshot is easy to explain. Mention the other two and say why you chose this one.
Bellman-Ford in general — run it V − 1 rounds for shortest paths with negative weights. A further round that still improves something means a negative cycle, since no simple path has more than V − 1 edges. That is how negative cycles are detected.
Path with Maximum Probability, Minimum Cost to Reach Destination in Time — the extended-state idea.
Real routing — the distance-vector protocols behind RIP are Bellman-Ford, and their count-to-infinity problem is a direct consequence of it. Chapter 5.3.2.
"Why not Dijkstra?" A cheaper route may use too many hops. Give the concrete example from the problem statement.
"Why does Bellman-Ford fit?" After i rounds it knows the cheapest route using at most i edges, which is exactly the constraint.
"Why the snapshot?" Without it, one round can chain several flights and the hop count is meaningless. This is the question that separates people who understand the code from people who copied it.
"Could you still use Dijkstra?" Yes, with (node, flights used) as the state.
"How does Bellman-Ford detect a negative cycle?" An improvement on the V-th round.
One thing to volunteer: state the general rule. "A second constraint breaks Dijkstra's finalisation, so either count the constraint in rounds — Bellman-Ford — or fold it into the state." That sentence covers a whole family of problems.
Next:4.22 is the chapter most people find hardest, so it is built from the ground up — what makes a problem dynamic programming rather than greedy, the five questions that produce the recurrence, and the four forms the same solution can take.