Cheapest Flights Within K Stops

Bounded breadth-first search — enumerate allowed routes

A direct baseline is a state search, where a state records the airport, price so far, and number of flights used. Breadth-first search expands states one flight-layer at a time and stops expanding after k + 1 flights.

This is a bounded BFS because the hop limit gives the search a hard depth. It is correct, but dense flight maps create a branching explosion: many different partial routes reach the same airport.

from collections import deque
 
 
def find_cheapest_price(
    n: int,
    flights: list[list[int]],
    src: int,
    dst: int,
    k: int,
) -> int:
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for start, end, price in flights:
        graph[start].append((end, price))
 
    queue = deque([(src, 0, 0)])
    answer = float("inf")
    while queue:
        airport, price, flights_used = queue.popleft()
        if airport == dst:
            answer = min(answer, price)
        if flights_used == k + 1:
            continue
        for next_airport, ticket_price in graph[airport]:
            queue.append((next_airport, price + ticket_price, flights_used + 1))
 
    return -1 if answer == float("inf") else int(answer)

Time O(V^(k+1)) in a dense graph because the search may branch to nearly every airport at each layer. Space O(V^(k+1)) for the queued route states.

Limited Bellman-Ford — one relaxation round per flight

Bellman-Ford is the right choice because the constraint is a bound on the number of edges. One relaxation round extends every already-known route by at most one flight. Run k + 1 rounds, and the distance to dst is the cheapest price using at most that many flights.

def find_cheapest_price(
    n: int,
    flights: list[list[int]],
    src: int,
    dst: int,
    k: int,
) -> int:
    prices = [float("inf")] * n
    prices[src] = 0
 
    for _ in range(k + 1):
        next_prices = prices.copy()
        for start, end, ticket_price in flights:
            candidate = prices[start] + ticket_price
            if candidate < next_prices[end]:
                next_prices[end] = candidate
        prices = next_prices
 
    return -1 if prices[dst] == float("inf") else int(prices[dst])

The copy is the guardrail. If you updated prices in place, a newly improved airport could feed another flight during the same round, silently spending multiple flights.

Plain Dijkstra isn't enough here. Keeping only the cheapest price per airport can discard a costlier arrival that used fewer flights and still has enough hop budget to reach dst. You could add flights-used to Dijkstra's state, but limited Bellman-Ford models this particular constraint more directly.

Time O(kE) — k + 1 passes over E flights. Space O(V) for the current and next price arrays.