Cheapest Flights Within K Stops

Cheapest Flights Within K Stops is a graph problem with a twist: it is a shortest-path question, but with a hard cap on how many hops you may take. That cap is exactly what makes plain Dijkstra awkward and Bellman-Ford a perfect fit.

The slow way first

You could try every possible route from src with a DFS, tracking the cost and the number of stops, and keep the cheapest one that stays within k stops. But the number of routes explodes — it is exponential in the worst case, far too slow for a dense graph.

The question to ask: can I find the cheapest price one hop at a time, so the stop limit falls out naturally? That is exactly what Bellman-Ford does.

The idea: relax all edges, k + 1 times

Keep a dist array where dist[v] is the cheapest price to reach city v so far. Start dist[src] = 0 and everything else infinity.

Now run k + 1 rounds. In each round, look at every flight u → v and try to relax it: if reaching u plus the flight price is cheaper than the best price we have for v, update dist[v]. The crucial trick: each round relaxes using a frozen copy of the previous round's distances. That guarantees each round adds at most one hop, so after k + 1 rounds dist[dst] is the cheapest price using at most k stops.

Why k + 1 and not k? A route with k stops has k + 1 flights (edges). Each round propagates one edge, so we need k + 1 rounds to let a price travel along the full route.

Walk through it

Step through the animation. City 0 is the source (price 0); city 3 is the destination. In round 1, edges 0 → 1 and 0 → 2 relax, so dist becomes [0, 100, 500, ∞] — but the edges into 3 cannot fire yet, because the previous distances for 1 and 2 were still infinity. In round 2, the frozen prev = [0, 100, 500, ∞] finally lets 1 → 3 relax: 100 + 100 = 200. The edge 2 → 3 would give 600, which loses. After 2 rounds, dist[3] = 200.

Pseudocode

dist = array of infinity, length n
dist[src] = 0
repeat (k + 1) times:
    prev = a copy of dist           # freeze this round's starting point
    for each flight (u, v, price):
        if prev[u] is infinity:     # u not reachable yet
            skip
        if prev[u] + price < dist[v]:
            dist[v] = prev[u] + price
return dist[dst] if it is not infinity else -1

The Python solution

def find_cheapest_price(n, flights, src, dst, k):
    dist = [float("inf")] * n
    dist[src] = 0
    for _ in range(k + 1):
        prev = dist.copy()
        for u, v, price in flights:
            if prev[u] == float("inf"):
                continue
            if prev[u] + price < dist[v]:
                dist[v] = prev[u] + price
    return dist[dst] if dist[dst] != float("inf") else -1

• dist starts as all infinity except dist[src] = 0 — we know nothing yet except that the source costs nothing.
• The outer loop runs exactly k + 1 times — one round per allowed hop.
• prev = dist.copy() is the heart of the trick: relaxing against a frozen snapshot stops a single round from chaining two hops together. Without it, a price could race across the whole graph in one round and overshoot the stop limit.
• For each flight, if u is not yet reachable in prev we skip; otherwise we relax v if going through u is cheaper.
• At the end, dist[dst] is the cheapest price within k stops, or -1 if it is still infinity.

Complexity

With E flights and k + 1 rounds, the work is O(k * E). The space is O(n) for the dist array (plus its single copy per round).

When this pattern shows up

Practice