Cheapest Flights Within K Stops
Find the cheapest route with at most k stops using Bellman-Ford limited to k + 1 rounds: each round lets every route take one more flight.
Problem Understanding
Cheapest Flights Within K Stops: there are n cities and flights[i] = [from, to, price]. Return the cheapest price from src to dst with at most k stops in between, or -1 if there is no such route.
Example: with flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1, the answer is 700 (0 → 1 → 3). The cheaper 0 → 1 → 2 → 3 costs 400 but has 2 stops.
The Intuition: Grow Routes One Flight at a Time
k stops is the same as at most k + 1 flights. So build the answer by number of flights:
- Before any flight, only
srcis reachable, for 0. - Each round, every flight
u → voffersprice[u] + wforv, using the prices from the previous round. - After round
i, every price is the cheapest route that uses at mostiflights.
Stop after k + 1 rounds. This is Bellman-Ford with a round limit, and it explores the graph level by level like breadth-first search, where each level is one more flight. Compare Network Delay Time, where there is no stop limit and Dijkstra's heap is the better tool.
Interactive Walkthrough
Each row holds the cheapest prices using at most that many flights. The dashed row is being built: a flight reads its departure price from the row above and writes into the dashed row. Try More stops to see a 3-flight route undercut the 1-stop answer.
Dry Run Table
Input: example 1, src = 0, dst = 3, k = 1 (at most 2 flights)
| Prices | City 0 | City 1 | City 2 | City 3 |
|---|---|---|---|---|
| start | 0 | ∞ | ∞ | ∞ |
| ≤ 1 flight | 0 | 100 | ∞ | ∞ |
| ≤ 2 flights | 0 | 100 | 200 | 700 |
- Round 2 reads city 2 from the row above, where it is still ∞, so
2 → 3cannot be used yet. - City 3 gets
100 + 600 = 700through1 → 3.
Answer: 700.
The Solution Template
k + 1 rounds over the flight list, each reading the previous round's prices. Java, C++ and C check for the infinity sentinel before adding, to avoid overflow.
Cheapest Flights Within K Stops Code
1var findCheapestPrice = function(n, flights, src, dst, k) {2 let prices = Array(n).fill(Infinity);3 prices[src] = 0;4 for (let i = 0; i <= k; i++) {5 const tmp = [...prices];6 for (const [u, v, w] of flights) {7 if (prices[u] + w < tmp[v]) tmp[v] = prices[u] + w;8 }9 prices = tmp;10 }11 return prices[dst] === Infinity ? -1 : prices[dst];12};
Edge Cases & Common Mistakes
- Relaxing in place: without the copy, one round can chain several flights and break the stop limit.
- k + 1, not k:
kcounts stops between flights; the number of flights isk + 1. - Unreachable dst: return
-1when the price is still infinity. - Overflow with INT_MAX: check that the departure city is reachable before adding the price.
- Plain Dijkstra: settles each city at its cheapest price regardless of stops and can miss a valid, pricier route.
Summary
Run Bellman-Ford for exactly k + 1 rounds. Each round copies the prices and relaxes every flight from the old copy, so routes grow by one flight per round. Return prices[dst], or -1 if unreachable. O(k · E) time, O(n) space.
More practice: DSA interview questions with answers · patterns cheat sheet