Problem 49 · Graphs

Cheapest Flights Within K Stops

MediumClassic DSA & systems

01Problem

Given flights (from, to, price), find the cheapest price from src to dst using at most k stops, or -1 if none exists.

02Key insight

The stop limit breaks plain Dijkstra's state. Bellman-Ford limited to k+1 relaxation rounds, copying the previous round's array so each round adds exactly one edge, solves it cleanly.

03Solution

solution.pypython11 lines

def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    INF = float("inf")
    cost = [INF] * n
    cost[src] = 0
    for _ in range(k + 1):
        nxt = cost[:]  # relax from previous round only: at most one more edge
        for u, v, price in flights:
            if cost[u] + price < nxt[v]:
                nxt[v] = cost[u] + price
        cost = nxt
    return -1 if cost[dst] == INF else int(cost[dst])

Try it first.

TimeO(k*E)

SpaceO(V)

tests.py · 4 passing

tests.pypython5 lines

flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
assert find_cheapest_price(4, flights, 0, 3, 1) == 700
assert find_cheapest_price(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1) == 200
assert find_cheapest_price(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) == 500
assert find_cheapest_price(2, [], 0, 1, 3) == -1

04Staff-level follow-up

Real flight search adds time windows and layover rules: model state as (airport, time) in a time-expanded graph and run a label-setting search with Pareto-optimal (cost, stops) labels.