#787
Cheapest Flights Within K Stops
Medium Bellman-Ford with k+1 rounds
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Find the cheapest price from src to dst using at most k stops (k + 1 flights), or -1.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the cheapest route using at most k stops.
Why this works: Bellman-Ford's i-th round finds the best routes with at most i flights. Run k + 1 rounds, reading the previous round's prices.
Example: 0→1 (100), 1→2 (100), 0→2 (500), k = 1
round 1: price 1 = 100, price 2 = 500round 2: price 2 = min(500, 100+100) = 200
✦Hints open one at a time
Bellman-Ford's i-th round finds the best paths using at most i edges.
Run exactly k + 1 rounds, and relax from a copy of the previous round's prices so a round can't chain several flights.
↗Approach
prices[src] = 0. Repeat k + 1 times: copy the array, then for every flight (u, v, w) with prices[u] finite, update copy[v] = min(copy[v], prices[u] + w). Swap.
</>Solution (Java)
import java.util.*;
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] prices = new int[n];
Arrays.fill(prices, Integer.MAX_VALUE);
prices[src] = 0;
for (int round = 0; round <= k; round++) {
int[] next = prices.clone(); // read last round, write this round
for (int[] f : flights) {
int u = f[0], v = f[1], w = f[2];
if (prices[u] != Integer.MAX_VALUE && prices[u] + w < next[v]) next[v] = prices[u] + w;
}
prices = next;
}
return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
}
}!Common mistake
Updating the same array within a round, which lets one round use more than one extra flight.
Complexity
- Time: O(k · E).
- Space: O(V).
Topic: Graphs
🎬 Episodes 74–85: video coming soon