Cheapest Flights Within K Stops
Problem statement
There are n cities numbered 0 to n - 1, and flights lists one-way flights as [from, to, price]. Find the cheapest total price to get from city src to city dst using at most k stops, where a stop is an intermediate city (so a trip with k stops takes k + 1 flights). Return -1 if no trip within that limit exists.
The limit is what makes this harder than a plain shortest path: the cheapest route overall may need too many stops, and the best route with few stops may cost more.
Examples
Example 1
Input: n = 4, flights = [[0,1,100],[1,3,100],[0,2,50],[2,1,20],[2,3,200]], src = 0, dst = 3, k = 1
Output: 200
Explanation: With one stop, 0 → 1 → 3 costs 200 and 0 → 2 → 3 costs 250.
Example 2
Input: n = 4, flights = [[0,1,100],[1,3,100],[0,2,50],[2,1,20],[2,3,200]], src = 0, dst = 3, k = 2
Output: 170
Explanation: A second stop allows 0 → 2 → 1 → 3 for 50 + 20 + 100 = 170.
Hints
Approach
Bellman-Ford limited to k + 1 rounds. Keep price[city], the cheapest known cost with the flights used so far; start with 0 at src and infinity elsewhere.
Each round, copy price into nxt, then for every flight [u, v, w] set nxt[v] = min(nxt[v], price[u] + w). Reading from the old array and writing to the copy is the crucial detail: it stops a single round from chaining two flights together, so after round i every price uses at most i flights. After k + 1 rounds, price[dst] is the answer (or -1 if still infinite).
O(k · E)Space O(n)def find_cheapest_price(n, flights, src, dst, k): INF = float("inf") price = [INF] * n price[src] = 0 for _ in range(k + 1): nxt = price[:] for u, v, w in flights: if price[u] + w < nxt[v]: nxt[v] = price[u] + w price = nxt return -1 if price[dst] == INF else price[dst] flights = [[0, 1, 100], [1, 3, 100], [0, 2, 50], [2, 1, 20], [2, 3, 200]]print(find_cheapest_price(4, flights, 0, 3, 1))print(find_cheapest_price(4, flights, 0, 3, 2))Follow-up questions
- Return the actual route, not just its price.
- What if the limit is on total travel time instead of stops, with each flight having a duration?
Frequently asked questions
It is constrained routing: the cheapest path when the number of hops is capped, which comes up with request relays, TTL-limited forwarding and traffic that may cross only a few regions. It also tests whether you know why a textbook algorithm (Dijkstra) needs changing when a second constraint appears, which interviewers probe for.
Yes, if the state is (city, stops used) rather than just the city. Push (cost, city, stops) and allow a city to be revisited when it is reached with fewer stops than before. That works, but the bounded Bellman-Ford is shorter to write and easier to get right in an interview.
One round could use a price that was lowered earlier in the same round, chaining two or more flights. The round count would then no longer bound the number of flights, and you could return a trip with too many stops.