Cheapest Flights Within K Stops
There are n cities connected by flights, given as flightsi = [from, to, price]. You are given src, dst, and an integer k. Return the cheapest price from src to dst with at most k stops along the way, or -1 if no such route exists. This caps regular Bellman-Ford at k + 1 passes instead of running the usual n - 1: k stops means at most k + 1 flights, and each pass relaxes one more flight's worth of route. Relax from a snapshot of the previous pass's distances, so a single pass never chains more than one new flight onto a route.
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ flights.length ≤ n * (n - 1) / 2
- flightsi.length == 3
- 0 ≤ from, to ≤ n - 1
- 1 ≤ price ≤ 104
- 0 ≤ src, dst ≤ n - 1
- 0 ≤ k ≤ n - 1
Example
n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], src = 0, dst = 3, k = 1700Explanation With at most 1 stop, the only usable route is 0 → 1 → 3, costing 100 + 600 = 700.
In plain terms
- Stop
- A city you land in and take off from again, not counting the starting city or the final destination.
One relaxation pass per flight allowed, capped at k + 1
dist[0] = 0; every other city starts at infinity. k = 1 stop allows 2 passes.
What happens in this step
pass 1 of 2 begins (k = 1 stop allows k + 1 = 2 passes) dist[0] = 0 (source) dist[1] = dist[2] = dist[3] = ∞ Each pass relaxes every flight using a snapshot frozen at the start of the pass, so one pass can only add one more flight to any route — that's what keeps the stop count capped.
Steps to visualize
- Set distsrc = 0 and every other disti = infinity.
- Each pass, relax every flight using a snapshot of the distances from before this pass — never a value already updated in the same pass.
- Run exactly k + 1 passes (one flight per stop, plus the final landing).
- distdst after the last pass is the answer, or -1 if it is still infinity.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
dist[0] = 0; every other city starts at infinity. k = 1 stop allows 2 passes.
What happens in this step
pass 1 of 2 begins (k = 1 stop allows k + 1 = 2 passes) dist[0] = 0 (source) dist[1] = dist[2] = dist[3] = ∞ Each pass relaxes every flight using a snapshot frozen at the start of the pass, so one pass can only add one more flight to any route — that's what keeps the stop count capped.
Solution
function findCheapestPrice(n, flights, src, dst, k) {
let dist = new Array(n).fill(Infinity);
dist[src] = 0;
for (let i = 0; i <= k; i++) {
const next = dist.slice();
for (const [u, v, price] of flights) {
if (dist[u] !== Infinity && dist[u] + price < next[v]) {
next[v] = dist[u] + price;
}
}
dist = next;
}
return dist[dst] === Infinity ? -1 : dist[dst];
}- Time
- O(k * e)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
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 | example from the docstring |
n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1 | 200 | a 1-stop route beats the direct edge |
n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0 | 500 | k = 0 rules out the cheaper 1-stop route, forcing the direct edge |
n = 3, flights = [[0, 1, 100]], src = 0, dst = 2, k = 1 | -1 | destination is unreachable no matter how many stops are allowed |
n = 2, flights = [[0, 1, 10]], src = 0, dst = 0, k = 1 | 0 | source and destination are the same city |
n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 50]], src = 0, dst = 2, k = 1 | 50 | the direct edge is cheaper even though a detour is allowed |
n = 3, flights = [[0, 1, 100], [1, 2, 100]], src = 0, dst = 2, k = 0 | -1 | the only route needs 1 stop, but k = 0 forbids it |
n = 4, flights = [[0, 1, 100], [1, 2, 100], [2, 3, 100]], src = 0, dst = 3, k = 5 | 300 | k larger than needed still finds the same shortest route |