Cheapest Flight With a Limited Number of Layovers
Solve this ProblemYou are given the flights between n airports as a price matrix (0 means there is no flight). Find the cheapest way to fly from a source to a destination using at most k layovers, i.e. at most k + 1 flights, or -1 if that is impossible.
The cheapest route overall may use too many flights, so ordinary shortest-path search is not enough: the number of flights must be part of the state. Running Bellman-Ford for exactly k + 1 rounds does that.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ n ≤ 8 airports numbered 0 … n-1; prices is an n × n matrix: prices[u][v] = 0 means no flight from u to v, prices[u][v] = p (1 ≤ p ≤ 30) means a one-way flight costing p - ◆
0 ≤ src, dst < n and src ≠ dst; 0 ≤ k ≤ 6 is the largest allowed number of layovers (airports visited strictly between src and dst) - ◆
A route with at most k layovers therefore uses at most k + 1 flights - ◆
Return the cheapest total price of such a route, or -1 if there is none
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Route With at Most k + 1 Flights
BruteExplore every route that starts at the source, never visits an airport twice, and uses at most k + 1 flights. Add up the prices along the way and, whenever the destination is reached, keep the smallest total. This is a depth-first search that follows every flight from every airport, so the number of routes explodes with n and k.
O(n^(k+1))O(n)1class Solution {
2 private int best;
3
4 private void explore(int[][] prices, int u, int dst, int cost, int used, int limit, boolean[] onPath) {
5 if (u == dst) {
6 best = Math.min(best, cost);
7 return;
8 }
9 if (used == limit) return;
10 onPath[u] = true;
11 for (int v = 0; v < prices.length; v++) {
12 if (prices[u][v] > 0 && !onPath[v]) {
13 explore(prices, v, dst, cost + prices[u][v], used + 1, limit, onPath);
14 }
15 }
16 onPath[u] = false;
17 }
18
19 public int cheapestWithStops(int[][] prices, int src, int dst, int k) {
20 best = Integer.MAX_VALUE;
21 explore(prices, src, dst, 0, 0, k + 1, new boolean[prices.length]);
22 return best == Integer.MAX_VALUE ? -1 : best;
23 }
24}Optimal — Bellman-Ford Limited to k + 1 Rounds
OptimalLet the table after round r hold the cheapest price of reaching each airport using AT MOST r flights. Start with 0 for the source (round 0). Each round builds a new table from the previous one: from every reachable airport u, every flight u → v offers dist[u] + price to v. Using a fresh table matters: a flight added in this round must extend only routes from the previous round, otherwise a route could sneak in with more than r flights. After k + 1 rounds the table holds the best price with at most k + 1 flights (k layovers).
O((k + 1) · n²)O(n)1class Solution {
2 public int cheapestWithStops(int[][] prices, int src, int dst, int k) {
3 int n = prices.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 for (int round = 0; round <= k; round++) {
9 int[] next = dist.clone();
10 for (int u = 0; u < n; u++) {
11 if (dist[u] == INF) continue;
12 for (int v = 0; v < n; v++) {
13 if (prices[u][v] > 0 && dist[u] + prices[u][v] < next[v]) {
14 next[v] = dist[u] + prices[u][v];
15 }
16 }
17 }
18 dist = next;
19 }
20 return dist[dst] == INF ? -1 : dist[dst];
21 }
22}