DSA Tracker

Visualize

Cheapest Flights Within K Stops

Bellman-Ford capped at k+1 rounds: one more flight allowed per round

time O(k * E)space O(V)

The catch is not cheapest price alone — Dijkstra would lock in the direct 500 flight as final the moment it is the smallest tentative distance, and never look back once a cheaper-but-longer route needs one more flight than it has already used. Bellman-Ford sidesteps that by bounding ROUNDS instead of vertices: run exactly k+1 relaxation rounds, where each round lets every flight try to improve a price using ONLY the prices frozen at the start of that round. That freeze is what caps a path at one extra flight per round, so after k+1 rounds every price reflects the cheapest route using at most k+1 flights — exactly the k-stops limit.

Details

Animated on: 3 cities, flights 0->1 for 100, 1->2 for 100, 0->2 for 500, src = 0, dst = 2, at most k = 1 stop — find the cheapest price from 0 to 2.

Problem:Cheapest Flights Within K StopsMedium

Pattern:Shortest Path

Bellman-Ford capped at k+1 rounds: one more flight allowed per round

step 1 / 9

Cities and flight prices

3 cities, 3 flights, at most 1 stop allowed — that means at most 2 flights total. Find the cheapest price from 0 to 2.

Pseudocode
1FUNCTION cheapestFlight(n, flights, src, dst, k):
2  prices <- ARRAY OF n VALUES SET TO INFINITY
3  prices[src] <- 0
4  FOR round FROM 1 TO k + 1
5    temp <- COPY OF prices
6    FOR EACH (u, v, p) IN flights
7      IF prices[u] != INFINITY AND prices[u] + p < temp[v]
8        temp[v] <- prices[u] + p
9    prices <- temp
10  IF prices[dst] = INFINITY: RETURN -1
11  RETURN prices[dst]

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. 3 cities, 3 flights, at most 1 stop allowed — that means at most 2 flights total. Find the cheapest price from 0 to 2.
  2. Start every city at infinity except the source: prices[0] = 0. Bellman-Ford will run exactly k + 1 = 2 rounds — each round lets one more flight into a path.
  3. Round 1 begins by cloning prices into temp. Every relaxation this round reads from the FROZEN prices [0, inf, inf], never from temp — that is what stops two flights from being walked in one round.
  4. 0->1 costs 0+100=100, beating inf; 0->2 costs 0+500=500, beating inf.
  5. prices <- temp = [0, 100, 500]. That is the cheapest price to each city reachable using at most 1 flight.
  6. Round 2 begins by cloning prices into temp. Every relaxation this round reads from the FROZEN prices [0, 100, 500], never from temp — that is what stops two flights from being walked in one round.
  7. 1->2 costs 100+100=200, beating 500.
  8. prices <- temp = [0, 100, 200]. That is the cheapest price to each city reachable using at most 2 flights.
  9. After all 2 rounds, prices[2] = 200 is finite. RETURN 200.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Cheapest Flights Within K Stops in the editorAll Graph problemsBack to roadmap