Cheapest Flights Within K Stops

Use a layered dynamic program. The cost array holds the cheapest price to reach each city using the number of flights allowed so far. Start with the source at zero and everything else at infinity, then for each allowed flight count make a copy of the array and relax every flight into the copy, using the previous layer's values.

def find_cheapest_flight(n, flights, source, destination, k):
    cost = [float('inf')] * n
    cost[source] = 0
    for _ in range(k + 1):
        next_cost = list(cost)
        for u, v, price in flights:
            if cost[u] + price < next_cost[v]:
                next_cost[v] = cost[u] + price
        cost = next_cost
    return -1 if cost[destination] == float('inf') else cost[destination]


flights = [(0, 1, 100), (1, 2, 100), (2, 0, 100), (1, 2, 200)]
print(find_cheapest_flight(3, flights, 0, 2, 1))

The output is 200. With at most one stop, meaning at most two flights, the route from city zero through city one to city two costs two hundred, and the direct flight from one to two at that price is the only alternative that fits in the budget.

The mechanism is the copy. Each round writes into a fresh array, so a flight can only use the distances from the previous round. That is what enforces the limit on the number of flights, and using a single array in place would let a round chain several flights together and quietly exceed the budget.

The trade-off to name is the cost. The dynamic program is O of k times E time and O of n space, which is very good. The other approach is a breadth first search over the graph that tracks how many flights have been used, which is also linear in the number of states but explores many more of them. The point to get right is the convention on stops: k stops means k intermediate airports, so k plus one flights, which is why the loop runs k plus one times. Saying which convention you are using avoids the most common off by one in this problem.

Expand the graph level by level, where each level is one more flight. Carry the total price along with the node and the number of flights used so far, and keep the cheapest price seen for the destination.

from collections import deque


def find_cheapest_flight(n, flights, source, destination, k):
    graph = [[] for _ in range(n)]
    for u, v, price in flights:
        graph[u].append((v, price))
    queue = deque([(source, 0, 0)])
    best = float('inf')
    while queue:
        node, price, legs = queue.popleft()
        if node == destination:
            best = min(best, price)
            continue
        if legs == k + 1:
            continue
        for neighbour, cost in graph[node]:
            queue.append((neighbour, price + cost, legs + 1))
    return -1 if best == float('inf') else best


flights = [(0, 1, 100), (1, 2, 100), (2, 0, 100), (1, 2, 200)]
print(find_cheapest_flight(3, flights, 0, 2, 1))

The output is 200, the same as the dynamic program produced.

The mechanism is that the queue holds states of the form city, price and flights used. Expanding a state adds one flight, and the depth limit stops the expansion after k plus one flights. Because the search explores all routes within the budget, the cheapest price at which the destination is reached is the answer.

The trade-off to name is the number of states. The breadth first search explores every route within the limit, which is exponential in the number of flights allowed, while the dynamic program keeps only the cheapest price per city per layer and is therefore linear in the number of states. The search version is worth mentioning because it is the more intuitive one, but the dynamic program is the one to ship. As always, the stop convention matters: the guard uses k plus one legs because k stops means k intermediate airports.