Cheapest Flights Within K Stops

Share

Given n cities connected by flights with cost, find the cheapest price from src to dst with at most k stops. Return -1 if impossible.

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
Example 2
Input: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1 → Output: 200

Solution Approach

Bellman-Ford with at most k+1 relaxations. Use a temporary array to avoid using edges from the current round.

  • Initialize prices[] with INF, prices[src]=0.
  • Repeat k+1 times: copy prices to temp; for each flight [u,v,cost]: if prices[u]+cost < temp[v]: temp[v]=prices[u]+cost.
  • Set prices = temp.
  • Return prices[dst] or -1 if INF.
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 i = 0; i <= k; i++) {
            int[] temp = prices.clone();
            for (int[] f : flights) {
                if (prices[f[0]] != Integer.MAX_VALUE && prices[f[0]] + f[2] < temp[f[1]])
                    temp[f[1]] = prices[f[0]] + f[2];
            }
            prices = temp;
        }
        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}
  • Time Complexity: O(K * E)
  • Space Complexity: O(N)