Cheapest Flights Within K Stops

Explore every path from src via DFS, tracking how many stops remain, and memoize on (current city, stops remaining) since the cheapest cost to reach dst from a given city with a given stop budget doesn’t depend on how you got there.

from collections import defaultdict

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in flights:
            graph[u].append((v, w))

        memo = {}

        def dfs(node: int, stops: int) -> float:
            if node == dst:
                return 0
            if stops < 0:
                return float('inf')
            if (node, stops) in memo:
                return memo[(node, stops)]

            best = float('inf')
            for nxt, price in graph[node]:
                cost = dfs(nxt, stops - 1)
                if cost != float('inf'):
                    best = min(best, price + cost)

            memo[(node, stops)] = best
            return best

        result = dfs(src, k)
        return -1 if result == float('inf') else result

Each of the O(V · k) distinct (node, stops) states is computed once and reused; computing a state costs O(deg(node)), so total work is O(V · k + E · k) ≈ O(E · k) time in dense graphs, with O(V · k) space for the memo table plus recursion stack.

Bellman-Ford’s relaxation naturally models “at most k stops”: each round of relaxing every edge extends the reachable path length by exactly one edge. So running only k + 1 rounds (allowing up to k + 1 edges = at most k intermediate stops) directly enforces the stop limit, without needing to track (node, stops) pairs explicitly — the round number is the stop count.

The one subtlety: relax using a snapshot of the previous round’s distances, not the array being updated in place. Otherwise a single round could chain multiple edge relaxations together, silently using more “hops” than that round is supposed to represent.

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        dist = [float('inf')] * n
        dist[src] = 0

        for _ in range(k + 1):  # k stops = k + 1 edges
            new_dist = dist[:]  # snapshot: don't let this round chain onto itself
            for u, v, price in flights:
                if dist[u] != float('inf') and dist[u] + price < new_dist[v]:
                    new_dist[v] = dist[u] + price
            dist = new_dist

        return dist[dst] if dist[dst] != float('inf') else -1

Tracing n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1 (2 rounds = k + 1): watch the frozen snapshot. Every relaxation reads only those slate values, while each update lands in the separate building row below — so one round can never chain two edges into the same path, which is the whole reason 0→1→2→3 cannot sneak past the stop limit.

After 2 rounds, dist[3] = 700 — matching the expected output. The tempting path 0→1→2→3 costs 100 + 100 + 200 = 400 — genuinely cheaper — but it uses 3 edges (2 stops), and a path only gains one edge per round from the fixed starting snapshot, so reaching it would need a third round that k = 1 forbids.

Why it’s correct: by induction, after round i, dist[v] holds the cheapest cost to reach v using at most i edges — a direct consequence of the Bellman-Ford invariant, here deliberately capped at k + 1 rounds instead of running to convergence (n - 1 rounds) specifically to enforce the stop constraint.

Complexity: k + 1 rounds, each scanning all E edges — O(k · E) time (and since k < n, this is also bounded by the more familiar O(n · E)). Space is O(V) for the two distance arrays, versus O(V · k) for the memoized DFS — the main advantage of this approach.