Cheapest Flights Within K Stops
Cheapest Flights Within K Stops is LeetCode 787 (Medium). There are n cities and a list flights where flights[i] = [from, to, price] is a one-way flight. Return the cheapest price from src to dst using at most k stops, or -1 if there is no such route.
kstops means at mostk + 1flights.- Prices are positive;
nis at most 100. - The cheapest route overall may use too many stops, so a plain shortest path is not enough.
- 2 <= n <= 100
- 0 <= flights.length <= (n * (n - 1) / 2)
- flights[i].length == 3
- 0 <= fromi, toi < n
- fromi != toi
- 1 <= pricei <= 10⁴
- There will not be any multiple flights between two cities.
- 0 <= src, dst, k < n
- src != dst
Intuition
Without the stop limit this is a normal shortest path. The limit adds a second rule: a route may use at most k + 1 flights.
Bellman-Ford handles that rule naturally because it works in rounds. After round r, every city holds the cheapest price using at most r flights. So run exactly k + 1 rounds and read the price of dst. The only care needed is that each round extends a route by one flight, never more.
"Shortest path with at most k edges" is Bellman-Ford with the number of rounds as the limit, using a copy of the distances each round. If the limit were on something else, such as fuel or time, the usual fix is to put it in the state, as in the Dijkstra version below, so each (city, used) pair is its own node.
Approach
Before reading on: in the first example, the cheapest route from 0 to 3 costs 400 but uses three flights. With k = 1, which route is allowed, and what would make an algorithm pick the 400 route by mistake?
Two ways to solve it
Each round lets every route take one more flight, reading last round's prices and writing a copy.
- Limit: the round count enforces it.
- Memory: two arrays of size n.
- Code: two nested loops.
The simplest correct answer for LeetCode 787.
A min-heap of (price, city, flights used) pops the cheapest route first and stops at dst.
- Limit: checked per heap entry.
- Memory: up to (k + 1) · E entries.
- Speed: often stops early.
The natural cheapest flights within k stops Dijkstra fix.
The rounds need no heap and enforce the stop limit by construction, so the steps, code and live demo below follow them. The Dijkstra code comes after the demo.
Start with the source only
Set dist[src] = 0 and every other city to infinity. These are the cheapest prices using zero flights: only the source is reachable.
Run k + 1 rounds on a copy
Each round starts with nxt = dist[:]. Read prices from dist, write them into nxt. Since dist only holds routes from the previous round, every route can grow by exactly one flight per round.
Try every flight
For each flight u → v with price w:
dist[u]is infinity: skip,uwas not reachable last round.dist[u] + w < nxt[v]: a cheaper route tov, so store it.- otherwise: keep the current price.
Finish the round, then answer
Set dist = nxt. After k + 1 rounds, dist[dst] is the cheapest price with at most k stops, or infinity if dst was never reached, in which case return -1. The time is O(k · E).
Cheapest Flights Within K Stops solution in Python | C++ | Java
k = 1 stops means at most 2 flights, so the loop runs 2 rounds, each allowing one more flight.dist into next. Every flight below reads prices from dist, which so far only holds the source, and writes to next. That way a route can grow by one flight per round and never more.next[1]; the route behind it uses at most 1 flight.next[1] already holds 100 from this round, but using it (100 + 100 = 200 for city 2) would chain two flights in one round and break the stop limit; that is why the code reads dist.next[1] already holds 100 from this round, but using it (100 + 600 = 700 for city 3) would chain two flights in one round and break the stop limit; that is why the code reads dist.next becomes dist: each price is now the cheapest route using at most 1 flight. The next round may add one more flight.dist into next. Every flight below reads prices from dist, which only holds routes of up to 1 flight, and writes to next. That way a route can grow by one flight per round and never more.next[2]; the route behind it uses at most 2 flights.next[2] already holds 200 from this round, but using it (200 + 100 = 300 for city 0) would chain two flights in one round and break the stop limit; that is why the code reads dist.next[3]; the route behind it uses at most 2 flights.next[2] already holds 200 from this round, but using it (200 + 200 = 400 for city 3) would chain two flights in one round and break the stop limit; that is why the code reads dist.next becomes dist: each price is now the cheapest route using at most 2 flights. No more rounds are allowed.k = 1 stops means at most 2 flights, so the loop runs 2 rounds, each allowing one more flight.dist into next. Every flight below reads prices from dist, which so far only holds the source, and writes to next. That way a route can grow by one flight per round and never more.next[1]; the route behind it uses at most 1 flight.next[1] already holds 100 from this round, but using it (100 + 100 = 200 for city 2) would chain two flights in one round and break the stop limit; that is why the code reads dist.next[2]; the route behind it uses at most 1 flight.next becomes dist: each price is now the cheapest route using at most 1 flight. The next round may add one more flight.dist into next. Every flight below reads prices from dist, which only holds routes of up to 1 flight, and writes to next. That way a route can grow by one flight per round and never more.next[2]; the route behind it uses at most 2 flights.next becomes dist: each price is now the cheapest route using at most 2 flights. No more rounds are allowed.k = 0 stops means at most 1 flight, so the loop runs 1 round.dist into next. Every flight below reads prices from dist, which so far only holds the source, and writes to next. That way a route can grow by one flight per round and never more.next[1]; the route behind it uses at most 1 flight.next[1] already holds 100 from this round, but using it (100 + 100 = 200 for city 2) would chain two flights in one round and break the stop limit; that is why the code reads dist.next[2]; the route behind it uses at most 1 flight.next becomes dist: each price is now the cheapest route using at most 1 flight. No more rounds are allowed.Dijkstra with a stop count
Heap entries carry the flights used so far. The first time dst is popped its price is the answer. A city is expanded again only if it is reached with fewer flights than before, since a later pop is never cheaper.
Common pitfalls
Relaxing in place
for u, v, w in flights:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wnxt = dist[:]
for u, v, w in flights:
if dist[u] != INF and dist[u] + w < nxt[v]:
nxt[v] = dist[u] + w
dist = nxtA price written earlier in the round is read again later in the same round, so one round can add several flights. In the first example this returns 400 (three flights) instead of 700.
Running k rounds instead of k + 1
for _ in range(k):
for _ in range(k + 1):
A direct flight has zero stops, so k stops allow k + 1 flights. With k rounds, k = 0 never even tries the direct flights and returns -1.
Dijkstra on price alone
heapq.heappush(heap, (cost + w, v))
heapq.heappush(heap, (cost + w, v, used + 1))
Plain Dijkstra keeps only the cheapest price per city. That price may need too many flights, while a pricier route with fewer flights, the only legal one, is thrown away. The number of flights has to be part of the state.
Complexity
Cheapest Flights Within K Stops FAQ
Can BFS solve the cheapest flights within k stops LeetCode problem?
Yes. Go level by level, where level r holds the cities reached with r flights, and stop after k + 1 levels. Keep a best price per city and only push a city again when its price improves. It does the same work as the rounds above, organised as a queue.