The problem
Given flights with prices between cities, find the cheapest price from city src to city dst using at most k stops in between. Return −1 if impossible.
Input: flights 0→1 $100, 1→2 $100, 2→0 $100, 1→3 $600, 2→3 $200; from 0 to 3, k = 1 Output: 700 (0 → 1 → 3)
Picture it
Picture a flight map. We relax prices in rounds: round 1 allows one flight, round 2 two flights, and so on up to k + 1 flights. Each round starts from a copy of the previous prices, so a single round can’t chain several flights together. The cheaper route 0 → 1 → 2 → 3 needs 2 stops, which is too many here.
How to recognise it
- A weighted directed graph (flights with prices) and a cheapest-route question.
- There is an extra limit on the number of edges used (at most k stops, so at most k + 1 flights).
- A route that is cheaper overall may use too many flights, so "cheapest" and "allowed" can disagree.
- Up to 100 cities and about 5,000 flights: a search over all routes is hopeless, but a few passes over the flights are cheap.
Start with brute force
Try every route: from the current city take every flight, stop when you have used k + 1 flights, and remember the cheapest total that ends at the destination.
def cheapest_brute(n, flights, src, dst, k):
best = inf
def go(city, flown, total):
nonlocal best
if city == dst:
best = min(best, total)
if flown == k + 1:
return
for a, b, cost in flights:
if a == city:
go(b, flown + 1, total + cost)
go(src, 0, 0)
return -1 if best == inf else best
If each city has up to d outgoing flights, there are up to d^(k+1) routes. With d near 99 and k up to 99 that is far beyond any limit. Space is O(k) for the recursion.
From brute force to the idea
- Find the waste. Many routes arrive at the same city having used the same number of flights, and only the cheapest of them matters for the future.
- Round r means "using at most r flights". Keep
price[c], the cheapest known price to reach city c with the flights allowed so far. At the start onlysrcis known, at price 0. - One round adds one flight. In each of the k + 1 rounds, look at every flight
(a, b, cost): if reachingaand then flying tobis cheaper than the current best forb, record it. - Use last round's prices. The line
nxt = price[:]makes a copy, and flights are relaxed frompriceintonxt. This guarantees that a round extends routes by exactly one flight, never two, so the flight limit is respected. - Read the answer. After k + 1 rounds,
price[dst]is the cheapest price using at most k + 1 flights. If it is stillinf, return -1.
The key idea: the best way to reach each city with at most r flights depends only on the best ways with at most r − 1 flights.
The key idea
Bellman–Ford limited to k + 1 rounds, using last round’s prices (a copy) for each relaxation.
Python solution
def find_cheapest_price(n, flights, src, dst, k):
price = [inf] * n
price[src] = 0
for _ in range(k + 1): # at most k stops = k+1 flights
nxt = price[:] # only build on last round’s prices
for a, b, cost in flights:
if price[a] + cost < nxt[b]:
nxt[b] = price[a] + cost
price = nxt
return -1 if price[dst] == inf else price[dst]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Try every route | O(d^(k+1)): every sequence of flights up to the limit | O(k): the recursion depth |
| Limited Bellman-Ford (shown code) | O((k + 1)·(E + n)): each round scans all flights and copies the price list | O(n): two price lists |
With 100 cities, 4,950 flights and k = 99 this is about 5 × 10^5 relaxations.
Edge cases
- Source equals destination (
src = dst): returns 0, with no flights. - No stops allowed (
k = 0): only direct flights count. For flights 0→1 (100), 1→2 (100), 0→2 (500), asking for 0 to 2 withk = 0gives 500, and withk = 1it gives 200. - Unreachable destination: returns -1.
- A cheaper route with too many flights is ignored, which is the whole point of the limit.
- Large k: extra rounds are harmless. They cannot make a price worse, since the copy keeps old prices.
- Imports:
inffrommath. Cities are numbered 0 to n − 1.
Common mistakes
- Running plain Dijkstra and ignoring the stop limit, which can return a cheaper route that uses too many flights.
- Writing into the same list that is being read (
nxt = price), which lets one round chain several flights. - Looping k times instead of k + 1 (k stops means k + 1 flights).
- Returning
price[dst]without translatinginfinto -1.
Return the cheapest price from src to dst using exactly m flights (not fewer), or -1 if impossible. A route may visit a city more than once. Describe what changes, then write it if you like.
Compare with our answer
The rounds stay, but each round must start fresh. Instead of copying the old prices (which allows "stay where you are"), start the next list at inf, so a city has a price only if it can be reached with exactly the number of flights flown so far.
def exactly(n, flights, src, dst, m):
price = [inf] * n
price[src] = 0
for _ in range(m):
nxt = [inf] * n
for a, b, cost in flights:
if price[a] + cost < nxt[b]:
nxt[b] = price[a] + cost
price = nxt
return -1 if price[dst] == inf else price[dst]
For flights 0→1 (100), 1→2 (100), 0→2 (500), exactly(3, flights, 0, 2, 1) is 500 and exactly(3, flights, 0, 2, 2) is 200. Time O(m·E), space O(n).
A strong answer mentions: starting each round with inf instead of a copy, the meaning of each round, and the O(m·E) cost.
1. A shipping network lists the cost of moving a package between ports. You need the cheapest way from port A to port B using at most 3 transfers. Which approach fits best?
The limit on transfers means the best route with at most r links must be built from the best with at most r − 1 links, which is limited Bellman-Ford. Plain Dijkstra may pick a cheaper route that uses too many transfers.
2. Why does the shown code write into nxt = price[:] and read from price?
If a flight updated price directly, a later flight in the same round could use that new price, which counts two flights as one round. The copy keeps rounds separate and enforces the limit.
3. A learner replaces nxt = price[:] with nxt = price. Which input now returns a wrong answer?
With the alias, the flight 0→1 updates price[1] and the next flight 1→2 uses it in the same round, so two flights are taken with k = 0. When the flights are listed in the other order, the second flight is read before it is updated.
Score 60% or more and the lesson is marked complete.