Bellman-Ford with a boarding-pass budget: relax every flight once per pass, always reading last pass's fares, and after exactly k+1 passes the destination's fare is the cheapest route that respects the stop limit.
K stops is a budget of k+1 flights — run Bellman-Ford for exactly k+1 rounds, each round reading a snapshot of the last.
Plain Dijkstra finds the cheapest route but counts no stops; DFS counts stops but enumerates everything. Notice what the constraint actually limits: edges. Bellman-Ford's outer loop is literally indexed by edges used — after pass i, dist[v] is the cheapest fare to v using at most i flights. The algorithm fits the problem exactly; you just stop it early, at k+1 passes instead of n−1.
dist into prev. Flight u→v improves v only if prev[u] + price beats dist[v] — reading the snapshot caps every route at one new flight per pass.dist[dst] is the answer — still ∞ means no route fits the budget, so return −1.The canonical example hides a trap: ignoring stops, the cheapest route is 0→1→2→3 for 400 — but it burns 2 stops and the budget is k=1. Step through and watch the snapshot refuse to chain that route; the legal answer is 700.
class Solution:
def findCheapestPrice(self, n, flights, src, dst, k):
INF = float('inf')
dist = [INF] * n
dist[src] = 0 # only the source costs 0 with 0 flights
for _ in range(k + 1): # k stops ⇒ k+1 flights allowed
prev = dist[:] # snapshot: this pass reads last pass only
for u, v, price in flights:
if prev[u] + price < dist[v]:
dist[v] = prev[u] + price # relax: reach v via u
return -1 if dist[dst] == INF else dist[dst]An early exit (stop when a pass changes nothing) is a safe micro-optimization but proves nothing new — mention it, don't lead with it. Dijkstra also works if the state becomes (city, stops used); bounded Bellman-Ford is shorter to write and far easier to prove correct under a stop limit.
k stops ⇒ k+1 flightsA stop is an intermediate city, so the route src … dst may use at most k+1 edges. The fare table must never reflect more than that.prev = dist[:]Pass i reads only prev — the fares banked after pass i−1 — so one pass can never chain two flights. Updating in place would silently overspend the budget.dist[v] = min(dist[v], prev[u] + price)Flight u→v offers city v a candidate: reach u within i−1 flights, then take this one. Keep it only if it beats every offer seen so far.The trap case. The unrestricted cheapest route 0→1→2→3 costs 400 but needs 2 stops — over budget. Within 1 stop the best is 0→1→3 = 700, and the snapshot is exactly what forbids chaining 0→1 and 1→2 in a single pass.
Zero stops means direct flights only, so only one pass runs. The 200 layover route never enters the table; the direct flight's 500 is the answer. Same input with k=1 returns 200 instead.
"K stops is really an edge budget of k+1, and Bellman-Ford spends that budget one edge per pass. As long as each pass relaxes from a snapshot of the previous one, pass i can never use more than i flights — so after k+1 passes, dist[dst] is my answer, or −1 if it's still infinity."