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_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.

Naive Solution (Brute Force)

A brute-force solution would involve exploring all possible paths from the source city to the destination city with at most k stops. This can be achieved using Depth-First Search (DFS). For each path, we calculate the total cost. The minimum cost among all valid paths (those with at most k stops) is the answer. However, this approach is highly inefficient due to the potentially exponential number of paths that need to be explored.

Code (Python)

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

    min_price = float('inf')

    def dfs(node, stops, cost):
        nonlocal min_price
        if node == dst:
            min_price = min(min_price, cost)
            return
        if stops < 0:
            return
        
        if node not in graph:
            return

        for neighbor, price in graph[node]:
            dfs(neighbor, stops - 1, cost + price)

    dfs(src, k, 0)

    return min_price if min_price != float('inf') else -1

Time Complexity

O(V^(K+1)), where V is the number of vertices (cities). In the worst case, we might explore all possible paths of length up to K+1.

Space Complexity

O(K), due to the recursion depth of the DFS.

Optimal Solution (Dynamic Programming / Bellman-Ford variant)

A more efficient solution can be obtained using dynamic programming or a variant of the Bellman-Ford algorithm. The idea is to iteratively relax the distances to all cities from the source city, considering at most k stops. We maintain an array dp where dp[i][city] represents the minimum cost to reach city from src using at most i stops. By iterating through the flights and updating the dp array, we can find the cheapest price to reach the destination with at most k stops.

Code (Python)

def find_cheapest_price(n, flights, src, dst, k):
    dp = [[float('inf')] * n for _ in range(k + 2)]
    for i in range(k + 2):
        dp[i][src] = 0

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

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

Time Complexity

O(K * E), where E is the number of flights. We iterate through the flights k+1 times.

Space Complexity

O(K * N), where N is the number of cities, due to the dp array.

Edge Cases

• If there is no path from src to dst, the algorithm should return -1.
• If k is 0, we should only consider direct flights from src to dst.
• The graph might contain cycles. The Bellman-Ford approach handles cycles correctly.
• src and dst are the same: return 0.