Cheapest Flights Within K Stops

Problem

There are n cities numbered 0 to n - 1, connected by directed flights. Each flight is given as [u, v, price]: you can fly from city u to city v for price dollars.

Given a start city src, a destination dst, and an integer k, return the cheapest total price to travel from src to dst using at most k intermediate stops — i.e. a route of at most k + 1 flights. If no such route exists, return -1.

Note that the globally cheapest route may use too many stops, so plain shortest-path logic is not enough.

Examples

• n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 → 700 — the cheaper route 0→1→2→3 (cost 400) needs 2 stops, so we must take 0→1→3.
• Same graph with k = 2 → 400 — now 0→1→2→3 is allowed.
• n = 3, flights = [[0,1,100],[1,2,100]], src = 0, dst = 2, k = 0 → -1 — reaching city 2 requires stopping at city 1.

Constraints

• 1 <= n <= 100
• 0 <= len(flights) <= n * (n - 1), no duplicate edges
• 1 <= price <= 10^4
• 0 <= k < n, src != dst

Think about it first

TL;DR

Bellman-Ford limited to k + 1 relaxation rounds — O(k · E) time, O(n) space.

Approach 1 — Brute force (DFS over all routes)

Try every route from src that uses at most k + 1 flights, tracking the running cost and keeping the best price that reaches dst. Pruning when the running cost already meets or exceeds the best found bounds the search (prices are positive).

def findCheapestPrice(n: int, flights: list[list[int]],
                      src: int, dst: int, k: int) -> int:
    adj = [[] for _ in range(n)]
    for u, v, price in flights:
        adj[u].append((v, price))

    best = [float("inf")]

    def dfs(node: int, edges_left: int, cost: int) -> None:
        if cost >= best[0]:
            return
        if node == dst:
            best[0] = cost
            return
        if edges_left == 0:
            return
        for nxt, price in adj[node]:
            dfs(nxt, edges_left - 1, cost + price)

    dfs(src, k + 1, 0)
    return -1 if best[0] == float("inf") else best[0]

Complexity: worst case O(n^(k+1)) time (branching factor up to n, depth k + 1), O(k) recursion space. With n = 100 and k up to 99, the number of routes is far too large to enumerate.

Approach 2 — Bellman-Ford, capped at k + 1 rounds

Bellman-Ford relaxes every edge once per round, and it has an invariant that fits this problem: after r rounds, dist[v] holds the cheapest cost to reach v using at most r edges. “At most k stops” is exactly “at most k + 1 edges”, so run exactly k + 1 rounds and stop. Within each round, relax against a snapshot of the previous round’s distances. Otherwise a single round could chain several new edges together and exceed the edge budget.

def findCheapestPrice(n: int, flights: list[list[int]],
                      src: int, dst: int, k: int) -> int:
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
        prev = dist[:]
        for u, v, price in flights:
            if prev[u] + price < dist[v]:
                dist[v] = prev[u] + price
    return -1 if dist[dst] == INF else dist[dst]

Walkthrough (n = 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1):

flowchart LR
    C0["city 0"] -->|100| C1["city 1"]
    C1 -->|100| C2["city 2"]
    C2 -->|100| C0
    C1 -->|600| C3["city 3"]
    C2 -->|200| C3

• Start: dist = [0, INF, INF, INF].
• Round 1 (snapshot [0, INF, INF, INF]): only edge 0→1 has a finite source, so dist = [0, 100, INF, INF].
• Round 2 (snapshot [0, 100, INF, INF]): 1→2 gives dist[2] = 200; 1→3 gives dist[3] = 700. dist = [0, 100, 200, 700].
• Two rounds = at most 2 flights = at most 1 stop. Answer: dist[3] = 700. The 400-cost route through city 2 needs a third flight, which the snapshot correctly excludes.

Complexity: O(k · E) time, O(n) space.

Approach 3 — Dijkstra on (city, edges-used) states

Ordinary Dijkstra (always settle the unvisited node with the smallest known distance, using a min-heap) breaks here because the cheapest way into a city may use too many edges. Make the state richer: run Dijkstra over pairs (city, edges used). The first time we pop dst its cost is optimal, because heap order is by cost. To prune, skip a state if we have already reached this city using fewer edges, since any route through it would have been found at cheaper-or-equal cost already.

import heapq

def findCheapestPrice(n: int, flights: list[list[int]],
                      src: int, dst: int, k: int) -> int:
    adj = [[] for _ in range(n)]
    for u, v, price in flights:
        adj[u].append((v, price))

    best_edges = [float("inf")] * n
    heap = [(0, 0, src)]  # (cost, edges used, city)
    while heap:
        cost, edges, node = heapq.heappop(heap)
        if node == dst:
            return cost
        if edges > k or edges >= best_edges[node]:
            continue
        best_edges[node] = edges
        for nxt, price in adj[node]:
            heapq.heappush(heap, (cost + price, edges + 1, nxt))
    return -1

Walkthrough (same example, k = 1): pop (0, 0, 0), push (100, 1, 1). Pop (100, 1, 1), push (200, 2, 2) and (700, 2, 3). Pop (200, 2, 2): edges = 2 > k, so skip; city 2 is unreachable within the budget. Pop (700, 2, 3): it is dst, return 700.

Complexity: each city can enter the heap once per edge count, so O(E · k) heap entries → O(E · k · log(E · k)) time, O(E · k) space. Fine here, but note Bellman-Ford is both simpler and asymptotically better for this problem.

Common pitfalls

• Relaxing against the live dist array instead of a snapshot — one Bellman-Ford round then chains multiple edges and violates the stop budget.
• Confusing stops with edges: k stops means k + 1 flights, so the loop runs k + 1 times.
• Using plain Dijkstra with a per-city visited set — it discards more-expensive-but-fewer-edges routes that are the only legal way to reach dst.
• Forgetting the unreachable case: return -1 when dst still holds infinity.

Pattern takeaway

When a shortest-path problem adds a budget (edge count, stops, fuel), the plain node-distance table is no longer a valid state space. Either bound the rounds of Bellman-Ford (each round = one more edge allowed) or expand Dijkstra’s state to (node, budget used). Bellman-Ford’s round-by-round invariant is the cleanest tool whenever the budget is on the number of edges.