Plain Dijkstra doesn’t directly apply here because the cheapest path might use more stops than a k-stop-respecting one — the stop limit changes which paths are even legal, so the state we search over must be (city, stops used so far), not just city. This is the same “resource-constrained shortest path” shape as Bellman-Ford’s round-by-round relaxation, which turns out to be exactly the right tool.
DFS with Memoization on (node, stops remaining)
Time O(V + E · k)Space O(V · k)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 resultEach 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, Limited to k + 1 Rounds
OptimalTime O(k · E)Space O(V)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 -1Tracing 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.
Frozen snapshot — every relaxation reads only these values
New distances — built one edge at a time
Edges — scanned in order
1/5 tested this roundRound 1 of 2 opens. The snapshot freezes the previous round result — `[0, ∞, ∞, ∞]` — and the new row below it is built one edge at a time. First edge `0→1`: the snapshot says `dist[0] = 0`, and `0 + 100 < ∞`, so `new[1] = 100` pops in (emerald). The snapshot itself never moves, because edges tested later this round must still see the old `∞`.
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.