Skip to content
AI360Xpert
Back to Advanced Graphs
Medium

Cheapest Flights Within K Stops

There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [fromi, toi, pricei]` indicates that there is a flight from city `fromi` to city `toi` with cost `pricei`. 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`.

Examples

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
The optimal path with at most 1 stop is 0 -> 1 -> 3 with cost 100 + 600 = 700. The path 0 -> 1 -> 2 -> 3 costs 400 but has 2 stops, which exceeds the limit k = 1.
Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output:200
The optimal path with at most 1 stop is 0 -> 1 -> 2 with cost 100 + 100 = 200.
Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output:500
With k = 0 stops, we can only take the direct flight 0 -> 2 which costs 500.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 10^4
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst < n
  • src != dst
  • 0 <= k < n

Bellman-Ford Algorithm (Modified)

Approach

Since we have a constraint on the number of stops (edges), Bellman-Ford is a natural fit. We maintain an array `prices` of size `n` initialized to infinity, except `prices[src] = 0`. We relax all edges exactly `k + 1` times (since `k` stops mean `k + 1` edges). Important: we must use a temporary `tmpPrices` array during each iteration to avoid chaining updates in the same iteration (which would represent taking multiple edges in a single step).

Complexity Analysis

Time Complexity
O(E * K)
Space Complexity
O(V)

Time complexity is O(E * K) where E is the number of flights (edges) and K is the number of stops allowed. We loop K + 1 times and iterate through all E edges. Space complexity is O(V) where V is the number of cities, to store the prices array.

Solution.java
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;                // Loop k + 1 times (for k stops)        for (int i = 0; i <= k; i++) {            // Create a copy to prevent using updated values from the same iteration            int[] tmpPrices = Arrays.copyOf(prices, n);                        for (int[] flight : flights) {                int u = flight[0];                int v = flight[1];                int p = flight[2];                                // If u is reachable, check if we can reach v cheaper                if (prices[u] != Integer.MAX_VALUE) {                    if (prices[u] + p < tmpPrices[v]) {                        tmpPrices[v] = prices[u] + p;                    }                }            }            prices = tmpPrices;        }                return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];    }}