LeetCode 787 · Advanced Graphs

Cheapest Flights Within K Stops, explained with a picture

The cheapest trip with a limited number of layovers.

MediumAdvanced Graphs
▶ Watch it step by step

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

  1. 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.
  2. 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 only src is known, at price 0.
  3. One round adds one flight. In each of the k + 1 rounds, look at every flight (a, b, cost): if reaching a and then flying to b is cheaper than the current best for b, record it.
  4. Use last round's prices. The line nxt = price[:] makes a copy, and flights are relaxed from price into nxt. This guarantees that a round extends routes by exactly one flight, never two, so the flight limit is respected.
  5. Read the answer. After k + 1 rounds, price[dst] is the cheapest price using at most k + 1 flights. If it is still inf, 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

ApproachTimeSpace
Try every routeO(d^(k+1)): every sequence of flights up to the limitO(k): the recursion depth
Limited Bellman-Ford (shown code)O((k + 1)·(E + n)): each round scans all flights and copies the price listO(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 with k = 0 gives 500, and with k = 1 it 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: inf from math. 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 translating inf into -1.
Your turn: exactly m flights

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.

Check what stuck

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?

2. Why does the shown code write into nxt = price[:] and read from price?

3. A learner replaces nxt = price[:] with nxt = price. Which input now returns a wrong answer?

Score 60% or more and the lesson is marked complete.