Cheapest Flights Within K Stops

Problem Description

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

---## Constraints

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

Bellman-Ford (k + 1 Relaxations)

Standard Dijkstra does not guarantee shortest path under a stop constraint because it might prioritize a longer path with fewer stops over a cheaper path with more stops.

The Bellman-Ford algorithm is a perfect fit here:

• Let prices be an array of size n initialized to infinity, and prices[src] = 0.
• At most k stops means we can use at most k + 1 flights.
• We run k + 1 iterations. In each iteration, we make a copy of the current prices array (tempPrices) to store updates. This ensures that updates in the current iteration only propagate using the state of the previous iteration (i.e. path of length i is built exactly on top of path of length i - 1).
• For each flight [u, v, price]:
  • If prices[u] != infinity, then tempPrices[v] = min(tempPrices[v], prices[u] + price).
• Update prices = tempPrices at the end of each iteration.
• Return prices[dst] (or -1 if it remains infinity).

Solution: Bellman-Ford

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;

        // k stops means at most k + 1 flights
        for (int i = 0; i <= k; i++) {
            int[] tempPrices = Arrays.copyOf(prices, n);

            for (int[] flight : flights) {
                int u = flight[0], v = flight[1], price = flight[2];
                if (prices[u] != Integer.MAX_VALUE) {
                    tempPrices[v] = Math.min(tempPrices[v], prices[u] + price);
                }
            }
            prices = tempPrices;
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        prices = [float('inf')] * n
        prices[src] = 0

        # k stops means at most k + 1 flights
        for _ in range(k + 1):
            temp_prices = list(prices)
            
            for u, v, price in flights:
                if prices[u] != float('inf'):
                    temp_prices[v] = min(temp_prices[v], prices[u] + price)
                    
            prices = temp_prices

        return prices[dst] if prices[dst] != float('inf') else -1

#include <vector>
#include <algorithm>

class Solution {
public:
    int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k) {
        std::vector<int> prices(n, 1e9);
        prices[src] = 0;

        for (int i = 0; i <= k; i++) {
            std::vector<int> tempPrices = prices;
            for (const auto& flight : flights) {
                int u = flight[0], v = flight[1], price = flight[2];
                if (prices[u] != 1e9) {
                    tempPrices[v] = std::min(tempPrices[v], prices[u] + price);
                }
            }
            prices = tempPrices;
        }

        return prices[dst] == 1e9 ? -1 : prices[dst];
    }
};

Complexity Analysis:

• Time Complexity: O(K * E) where K is the number of stops and E is the number of flights (edges).
• Space Complexity: O(N) to store the price array.

← All Problems