Cheapest Flights Within K Stops
Given flights [from, to, price], find the cheapest route from src to dst using at most k stops, or -1 if none exists.
Intuition
The reflex is Dijkstra, and here it is wrong. Dijkstra commits to the cheapest known cost for a city and never revisits it — but under a stop limit, an expensive route with few stops can be the only usable one, and Dijkstra will have already discarded it. The stop count is a second dimension the algorithm does not track. The fix is to relax the graph in rounds: after round i, the distance array holds the cheapest cost reachable using at most i flights. Run k + 1 rounds and read off the destination.
Bellman-Ford with the pass count as the constraint rather than a bound. After i relaxation rounds, dist holds the cheapest routes using at most i edges — exactly the quantity the problem limits. The snapshot copy is what enforces "at most one new edge per round".
Approach
See concretely why Dijkstra fails
Consider a graph where reaching city C costs 100 via a two-flight path and 500 via one direct flight, with k = 0 (no stops allowed). Dijkstra finalises C at 100 and never reconsiders it, so it either returns 100 — which violates the stop limit — or, with an added stop check, discards the only valid route. The problem is that cost alone is not enough state; the number of flights used matters too.
Relax in rounds, one flight per round
This is Bellman-Ford with a bounded iteration count. Initialise dist[src] = 0 and everything else to infinity. In each round, examine every edge and relax it. After round 1 the array holds the best cost using at most one flight, after round 2 at most two, and so on. Since k stops means at most k + 1 flights, run exactly k + 1 rounds.
Use a snapshot of the previous round
This is the detail that makes or breaks the solution. Within a round, all relaxations must read from the previous round's array, not the one being written. If you update in place, a chain of edges can be traversed inside a single round, quietly using more flights than the round number allows and producing routes that violate the stop limit. Copy the array at the start of each round and read from the copy. Cost: O(k x E).
Solution & live demo
Common pitfalls
Relaxing in place
for u, v, w in flights:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wnxt = dist[:]
for u, v, w in flights:
if dist[u] != INF and dist[u] + w < nxt[v]:
nxt[v] = dist[u] + w
dist = nxtAn in-place update lets a value improved earlier in the same round be used again later in that round, so one pass can traverse several edges. The route then exceeds the stop limit while appearing valid.
Running k rounds instead of k + 1
for _ in range(k):
for _ in range(k + 1):
k stops means k + 1 flights — a direct flight has zero stops. Off-by-one here rejects the longest legal route and returns a more expensive answer or −1.
Using Dijkstra on cost alone
heapq.heappush(pq, (cost, v))
for _ in range(k + 1): ...
Dijkstra finalises a node the first time it's popped, but the cheapest way to reach a node may use too many stops while a pricier route stays legal. Dijkstra only works here if the state includes the stop count.
Edge cases
One round runs, so only direct flights are considered — exactly right, since zero stops means one flight.
The entry stays at infinity after all rounds and -1 is returned.
The distance is 0 from initialisation and no relaxation improves it.
Harmless. The bounded round count prevents any route from using more than k + 1 edges, so cycles cannot be exploited or looped indefinitely.