Given flights with prices, find the cheapest price from src to dst using at most k stops. Return minus 1 if there is no such route.
DSA Animator › DSA Revision › Graph › Cheapest Flights Within K Stops
Remember: round r of Bellman Ford means at most r edges. Relax from a copy, so a single round never uses two flights. The video solves Cheapest Flights Within K Stops (LeetCode 787, Medium) with the Bellman-Ford with Rounds pattern from the Graph topic, and you can replay every step in the interactive Cheapest Flights Within K Stops animation.
Given flights with prices, find the cheapest price from src to dst using at most k stops. Return minus 1 if there is no such route.
With flights 0 to 1 for 100, 1 to 2 for 100, 2 to 0 for 100, 1 to 3 for 600 and 2 to 3 for 200, going from 0 to 3 with at most 1 stop costs 700. The route 0, 1, 2, 3 costs only 400, but it uses 2 stops, which is not allowed.
Plain Dijkstra finds the cheapest route, but it ignores the limit on stops. We need to control how many flights a route uses.
At most k stops means at most k plus 1 flights. Bellman Ford relaxes every flight once per round, and after r rounds it knows the best prices using at most r flights. So run exactly k plus 1 rounds. In each round, read prices from a copy of the previous round, so one round can never chain two flights together.
Start with price 0 for city 0, and infinity for the others. Round 1 uses one flight, so city 1 becomes 100. Round 2 reads the copy from round 1, so city 2 becomes 200, and city 3 becomes 100 plus 600, which is 700. The flight 2 to 3 would give 400, but city 2 only got its price in this same round. Because we read the copy, that third flight is not used. After k plus 1 rounds, the price for city 3 is 700.
In code, fill a price array with infinity, and set the source to 0. Repeat k plus 1 times: copy the array, and for each flight, relax the copy using the old prices. Replace the old array with the copy after each round. Return the price of dst, or minus 1, so it's O of k times the number of flights.
Remember: round r of Bellman Ford means at most r edges. Relax from a copy, so a single round never uses two flights.