Cheapest Flights Within K Stops
Problem statement
There are n cities, numbered 0 to n - 1, connected by one-way flights. Each flight is given as [from, to, price], meaning it costs price to fly directly from city from to city to.
Starting at city src, find the cheapest total price to reach city dst, using at most k stops along the way (so at most k + 1 flights total, since each stop is one extra flight). If no route reaches dst within that many stops, return -1.
Examples
Example 1
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: The cheapest route using at most 1 stop is 0 → 1 → 3, costing 100 + 600 = 700. The route 0 → 1 → 2 → 3 is cheaper overall (100+100+200=400) but uses 2 stops, which isn't allowed.

Example 2
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The route 0 → 1 → 2, using exactly 1 stop, costs 100 + 100 = 200, which is cheaper than the direct 500-cost flight.

Example 3
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: With no stops allowed, only the direct flight 0 → 2 can be used, costing 500.
Hints
Approach
Optimal: Bellman-Ford limited to k+1 rounds
Intuition
The everyday shortest-path shortcut — once you know a city's cheapest price, treat it as final and never look at it again — can actually give the wrong answer here. A cheap route to some city might already have used up too many stops to continue, while a slightly more expensive route to that same city might leave enough stops remaining to reach dst more cheaply overall. Dijkstra's algorithm relies on exactly that shortcut, which is why it isn't safe to use directly when there's a hard limit on the number of stops.
Bellman-Ford's relaxation idea sidesteps this by not finalizing anything early: it just repeatedly tries to improve every city's best-known price using every flight, for a fixed number of rounds. Doing exactly k + 1 rounds — one for each flight allowed, including the very last one to dst — directly encodes the stop limit into the algorithm itself, since no route can benefit from a round beyond the number of flights it's allowed to use.
The one subtlety is using each round's starting prices to compute that round's updates, rather than updating in place — otherwise a single round could accidentally chain together more than one flight's worth of improvement, which would let a route sneak past the stop limit.
Steps
- Set every city's best-known price to infinity, except
src, which starts at0. - Repeat
k + 1times:- Make a fresh copy of the current best-known prices, to be updated this round.
- For every flight
(u, v, price): ifu's price before this round is not infinity, check whether flying fromutovwould beatv's current best price in the copy, and update the copy if so. - Replace the best-known prices with this round's copy.
- After
k + 1rounds, returndst's best-known price, or-1if it's still infinity.
Dry run
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 (so 2 rounds)
| round | city 0 | city 1 | city 2 |
|---|---|---|---|
| start | 0 | inf | inf |
| after round 1 | 0 | 100 | 500 |
| after round 2 | 0 | 100 | 200 |
Round 1 only lets flights starting from src (city 0) improve anything, since every other city still has an infinite starting price that round. Round 2 then lets the newly-discovered price at city 1 improve city 2's price from 500 down to 200 (100 + 100), matching the expected output.
Edge cases: with k = 0, only a single round runs, so only direct flights from src can ever improve a price — matching example 3's result of 500, since city 2 never gets the chance to be improved through city 1 in just one round.
Complexity
Time O(k · E) - each of the k + 1 rounds relaxes every one of the E flights once, so the total work scales with the number of stops allowed times the number of flights.
Space O(n) - two arrays of size n (the current and next round's best-known prices) are kept, regardless of how many flights exist.
class Solution:
def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
INF = float("inf")
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1):
new_dist = dist.copy()
for u, v, w in flights:
if dist[u] != INF and dist[u] + w < new_dist[v]:
new_dist[v] = dist[u] + w
dist = new_dist
return dist[dst] if dist[dst] != INF else -1
if __name__ == "__main__":
print(Solution().findCheapestPrice(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1)) # 700
print(Solution().findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)) # 200
print(Solution().findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0)) # 500RecapThe whole problem in a few lines, for the night before
- Spot it: cheapest path in a weighted graph, but with a hard cap on the number of stops or edges allowed
- Idea: Bellman-Ford, limited to exactly k + 1 rounds of relaxation — each round represents one more flight becoming allowed
- Cost: O(k · E) time, O(n) space (exploring every route via DFS is exponential in the worst case)
- Trap: reaching for Dijkstra out of habit — its early-finalization shortcut can silently give a wrong (too-optimistic) answer once there's a cap on the number of stops
Interview follow-ups
What if instead of a hard cap on the number of stops, you just needed the plain cheapest price with no limit at all?
With no stop limit, Dijkstra's algorithm becomes safe to use again, since the early-finalization shortcut that caused trouble here only mattered because of the stop constraint. A standard Dijkstra with a min-heap, in O((V + E) log V) time, would be the more efficient choice once that constraint is removed.
What if you also needed to reconstruct the actual sequence of flights taken for the cheapest route, not just its price?
Alongside each city's best-known price, also track which flight most recently produced that price during the relaxation rounds. Once the algorithm finishes, walking backward from dst through those recorded flights, one step at a time, reconstructs the full route in reverse.
Frequently asked questions
Dijkstra's algorithm assumes that once a city's cheapest known price is found, it can never be improved later, so it finalizes that price and moves on. That assumption breaks here: a cheap route to a city might have already used up too many stops, while a pricier route to that same city might leave enough stops remaining to reach the destination more cheaply overall — something Dijkstra's early finalization can't account for.
Each round of relaxation represents one additional flight being allowed in a route: after 1 round, only direct flights from src can improve anything; after 2 rounds, routes with 1 stop can; and so on. Allowing at most k stops means allowing at most k + 1 flights total, which is exactly k + 1 rounds of relaxation.
Updating a city's price directly (in place) during a round means a later flight in that same round could immediately use the just-updated price, effectively letting one round secretly apply two flights' worth of improvement. Working from a fixed snapshot of the previous round's prices keeps each round to exactly one additional flight per route, which is what makes the stop limit correctly enforced.
Routing traffic or requests through a limited number of intermediate hops — a maximum number of service-to-service hops allowed before a request must be rejected, or the cheapest path through a limited number of proxy relays — is a direct real-world match for "cheapest path with a hard cap on stops", and recognizing that a naive Dijkstra-style shortcut breaks under that cap is exactly the insight this problem tests.