Cheapest Flights Within K Stops

Problem Description

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

Naive Approach (Brute Force)

A brute-force approach would involve exploring all possible paths from the source city to the destination city with at most k stops. This can be done using Depth-First Search (DFS). However, this approach is highly inefficient because it may explore the same paths multiple times, leading to exponential time complexity.

• Algorithm:

  1. Start DFS from the source city.
  2. Keep track of the current cost and the number of stops.
  3. If we reach the destination city within k stops, update the minimum cost.
  4. If the number of stops exceeds k, backtrack.

• Time Complexity: O(V^k), where V is the number of vertices (cities).

• Space Complexity: O(k), due to the recursion depth.

Optimal Approach (Dynamic Programming / Bellman-Ford)

A more efficient approach is to use dynamic programming or a variation of the Bellman-Ford algorithm. We can maintain an array dp[i][j] representing the minimum cost to reach city i with at most j stops. We can iterate through the flights and update the dp array.

• Algorithm:

  1. Initialize a dp array with dimensions (n x (k + 2)) with Infinity values. dp[src][0] should be 0, because it costs 0 to get to the start.
  2. Iterate from i = 1 to k + 1 (number of stops):
     • For each flight (u, v, price) in flights:
       • Update dp[v][i] = min(dp[v][i], dp[u][i-1] + price).
  3. The result is dp[dst][k+1]. If this is infinity, it means no path was found, return -1. Otherwise, return the result.

• Time Complexity: O(E * K), where E is the number of flights and K is the maximum number of stops.

• Space Complexity: O(N * (K + 1)), where N is the number of cities, to store the DP table.

Edge Cases

• No Path: If there is no path from the source to the destination within k stops, return -1.
• Source and Destination are the same: Although the constraints specify src != dst, handling this edge case would involve returning 0.
• Negative Flight Prices: While the problem statement specifies positive flight prices, handling negative cycles would require modifications to the algorithm (e.g., detecting negative cycles in Bellman-Ford).

Code (Python)

import heapq

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    graph = {}
    for u, v, w in flights:
        if u not in graph:
            graph[u] = []
        graph[u].append((v, w))

    # (cost, city, stops)
    pq = [(0, src, k + 1)]
    
    while pq:
        cost, city, stops = heapq.heappop(pq)
        
        if city == dst:
            return cost
        
        if stops > 0:
            if city in graph:
                for neighbor, price in graph[city]:
                    heapq.heappush(pq, (cost + price, neighbor, stops - 1))
    
    return -1

Code (DP - Python)

def findCheapestPrice_DP(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    dp = [[float('inf')] * (k + 2) for _ in range(n)]
    dp[src][0] = 0

    for i in range(1, k + 2):
        for u, v, price in flights:
            dp[v][i] = min(dp[v][i], dp[u][i-1] + price)

    ans = dp[dst][k+1]
    
    return ans if ans != float('inf') else -1