Q89: Cheapest Flights Within K Stops. - DSA Patterns (Multi-Lang)

In Simple Words: Bellman-Ford algorithm executed for $K + 1$ iterations. Maintain prices array and a temporary copy at each iteration to avoid using more than $K$ stops within the same relaxation pass.

Time: $O(K \cdot E)$ | Space: $O(V)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def findCheapestPrice(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    prices = [float('inf')] * n
    prices[src] = 0
    for _ in range(k + 1):
        tmp = prices.copy()
        for u, v, p in flights:
            if prices[u] == float('inf'): continue
            if prices[u] + p < tmp[v]:
                tmp[v] = prices[u] + p
        prices = tmp
    return prices[dst] if prices[dst] != float('inf') else -1