Find the cheapest fare with at most k stops. Relax every flight once per allowed hop, Bellman-Ford style, keeping last round's prices.
▼The problem
LeetCode 787 (Medium). There are n cities and a list of flights [from, to, price]. Return the cheapest price from src to dst with at most k stops (at most k + 1 flights), or -1 if there is no such route.
Example: 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 (0 → 1 → 3).
The solution
from math import inf
def findCheapestPrice(n, flights, src, dst, k):
price = [inf] * n
price[src] = 0
for day in range(k + 1):
new = price[:] # copy
for a, b, fare in flights:
if price[a] + fare < new[b]:
new[b] = price[a] + fare
price = new
return -1 if price[dst] == inf else price[dst]Transcript
Cheapest Flights Within K Stops. Given n cities and priced flights, find the cheapest trip from a source to a destination with at most k stops, or return minus one.
Take four cities. Flights go zero to one, one to two, and two to zero, for a hundred each; one to three for six hundred; and two to three for two hundred. Fly from zero to three with at most one stop. Zero, one, two, three costs four hundred, but that's two stops. So take zero, one, three: seven hundred.
The simple way: try every path with at most k stops. But paths multiply at every city: exponential. Plain Dijkstra, on cost alone, finds four hundred, ignoring the stop limit.
Instead, run Bellman-Ford for just k plus one rounds. Each round is one day of flights. Every flight tries to lower the price where it lands, using yesterday's prices.
In code, prices start at infinity; the source costs zero. Each round, copy the prices. For every flight, if yesterday's price at its start plus the fare is cheaper, update the copy. The copy stops one round from chaining two flights.
Day one: flight zero one sets city one to a hundred. Day two: city two gets two hundred, and city three gets seven hundred. Flight two three is skipped, since city two had no price yesterday. Without the copy, it would chain to four hundred. Answer: seven hundred.
Each round checks every flight once, so time is order k times E, the number of flights. Space is order n.
One flight per day, k plus one days. That's Cheapest Flights Within K Stops.