Cheapest flights within K stops

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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];
}