Cheapest flights within K stops
Problem
Given flights [from, to, price], a source, a destination and k, return the cheapest price from source to destination using at most k stops (k + 1 flights), or −1 if there is no such route.
Example 1
Input: n = 4, flights = [[0,1,100], [1,2,100], [2,0,100], [1,3,600], [2,3,200]], src = 0, dst = 3, k = 1 Output: 700
0 → 1 → 3. The cheaper 0 → 1 → 2 → 3 uses 2 stops.
Also asked as: Cheapest Flights Within K Stops
Test cases
Case 1
Input: 4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1 Expected: 700
Case 2
Input: 3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1 Expected: 200
Case 3
Input: 3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0 Expected: 500
Case 4
Input: 3, [[0,1,100]], 0, 2, 1 Expected: -1
View solutionHide solution1 approach
1. Bellman–Ford limited to K+1 relaxations
Time O(K · E)Space O(V)
Relax all edges K+1 times, but each round must read from the previous round’s distances (snapshot) so a path never uses more than K stops.
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 snap = dist.slice(); for (const [u, v, w] of flights) if (snap[u] + w < dist[v]) dist[v] = snap[u] + w; } return dist[dst] === Infinity ? -1 : dist[dst];}