Course4all
Join us on telegram
Home/dsa/Graphs/Cheapest Flights Within K Stops

Cheapest Flights Within K Stops

Master this topic with zero to advance depth.

Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i.

You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Visual Representation

(0) --100--> (1) --100--> (2) | ^ |----------500------------| K = 1: Path 0 -> 1 -> 2: Price 200. Stops: 1 (OK) Result: 200 K = 0: Path 0 -> 2: Price 500. Stops: 0 (OK) Path 0 -> 1 -> 2: Stops: 1 (FAIL) Result: 500
Medium

Examples

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200

0 to 1 then to 2 is cheapest within 1 stop.

Approach 1

Level I: Brute Force (BFS with Depth)

Intuition

We can use BFS to explore paths level by level. Each level represents one 'stop'. We stop exploring when we exceed KK stops.

Thought Process

  1. Build adjacency list.
  2. Queue stores (node, current_price, current_stops).
  3. Keep a min_prices array to prune paths that are more expensive than what we've seen at a certain node.
  4. While queue is not empty:
    • Pop (u, price, stops).
    • If stops > k, skip.
    • For each neighbor v with flight cost w:
      • If price + w < min_prices[v]:
        • min_prices[v] = price + w.
        • Push (v, price + w, stops + 1).

Pattern: Level-wise BFS

⏱ O(E * K) - Similar to Bellman-Ford in effect.💾 O(V * K) - In worst case queue size.

Detailed Dry Run

k=1, src=0, dst=2, edges=[[0,1,100],[1,2,100],[0,2,500]]

  1. Queue: [(0, 0, -1)] (stops starts at -1 as first flight is 0 stops)
  2. Pop (0,0,-1). Neighbors: (1, 100, 0), (2, 500, 0). min_prices: {1:100, 2:500}
  3. Pop (1,100,0). Neighbors: (2, 200, 1). 200 < 500. min_prices: {2:200}
  4. Pop (2,500,0). Neighbors: None.
  5. Pop (2,200,1). Stops = k. Done. Result: 200
java
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<int[]>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});
        
        int[] minPrices = new int[n];
        Arrays.fill(minPrices, Integer.MAX_VALUE);
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{src, 0, -1});
        
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int u = curr[0], price = curr[1], stops = curr[2];
            if (stops >= k) continue;
            for (int[] next : adj[u]) {
                int v = next[0], w = next[1];
                if (price + w < minPrices[v]) {
                    minPrices[v] = price + w;
                    q.add(new int[]{v, price + w, stops + 1});
                }
            }
        }
        return minPrices[dst] == Integer.MAX_VALUE ? -1 : minPrices[dst];
    }
}
Approach 2

Level III: Optimal (Bellman-Ford / BFS)

Intuition

Dijkstra focuses on shortest distance, but here we have a constraint on the number of edges (stops). Bellman-Ford is perfect for this: we run the relaxation process exactly k+1 times to find the shortest path with at most k edges.

Thought Process

  1. Initialize prices array with infinity, prices[src] = 0.
  2. For i from 0 to k:
    • Create a temp copy of prices to avoid using updated prices from the SAME iteration (level-wise relaxation).
    • For each flight (u, v, cost):
      • If prices[u] is not infinity, update temp[v] = min(temp[v], prices[u] + cost).
    • Set prices = temp.
  3. Return prices[dst] if reachable, else -1.

Pattern: Constrained Shortest Path

⏱ O(K * E) where E is number of flights.💾 O(N) for price array.

Detailed Dry Run

k=1, src=0, dst=2, flights=[[0,1,100],[1,2,100],[0,2,500]]

Iter012Actions
Init0infinf-
10100500Relax edges from 0
20100200Relax edge 1->2 (100+100=200)
Result: 200
java
import java.util.*;

public 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 i = 0; i <= k; i++) {
            int[] temp = Arrays.copyOf(prices, n);
            for (int[] f : flights) {
                int u = f[0], v = f[1], cost = f[2];
                if (prices[u] == Integer.MAX_VALUE) continue;
                temp[v] = Math.min(temp[v], prices[u] + cost);
            }
            prices = temp;
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}
← Previous QuestionNetwork Delay Time
Next Question →Word Ladder