Cheapest Flights Within K Stops (LeetCode 787)

The problem

There are n cities and a list of flights, each [from, to, price] (one-way). Find the cheapest price to fly from src to dst using at most k stops in between. If no such route exists, return -1.

Input:  n = 4
        flights = [[0,1,100], [1,2,100], [2,0,100], [1,3,600], [2,3,200]]
        src = 0, dst = 3, k = 1
Output: 700

0 → 1 → 2 → 3 costs only 400, but it has two stops (1 and 2). With at most one stop, the best is 0 → 1 → 3 for 700.

How to think about it

Start with brute force. Explore every route from src with up to k + 1 flights and keep the cheapest that ends at dst. With branching factor b, that’s O(b^(k+1)) routes. Too slow when k is large.

Why plain Dijkstra struggles. Dijkstra finalises a city the first time it’s popped at its cheapest price. But the cheapest way to reach a city might use too many stops, while a pricier way with fewer stops is the only one that can still get to dst in time. In the example, city 2 is cheapest via 0 → 1 → 2 (200), but that leaves no stops for the final leg. Dijkstra can be patched by putting stops in the state, but it’s easy to get wrong.

The key insight: “at most k stops” means “at most k + 1 edges”, and Bellman-Ford counts edges. In Bellman-Ford, after round i, dist[v] is the cheapest cost to reach v using at most i edges. So run exactly k + 1 rounds. Each round, try every flight u → v and see if dist[u] + price improves v.

The snapshot is what makes it correct. If you update dist in place during a round, a city improved earlier in the same round can be used again later in that round, chaining two flights into one round. Copy dist to tmp at the start of the round, read from dist, write to tmp, then swap. Now each round adds exactly one more edge at most.

Which pattern is this? Shortest path with an edge limit: Bellman-Ford. The tell is “cheapest path with at most K stops / K edges”.

Approach

1. Set dist[src] = 0 and every other city to infinity.
2. Repeat k + 1 times: copy dist into tmp. For each flight (u, v, w), if dist[u] + w < tmp[v], set tmp[v] = dist[u] + w. Then dist = tmp.
3. Return dist[dst], or -1 if it’s still infinity.

Solution

def find_cheapest_price(n, flights, src, dst, k):
    dist = [float('inf')]*n; dist[src] = 0
    for _ in range(k + 1):                        # k stops = at most k+1 flights
        tmp = dist[:]                             # snapshot: read old, write new
        for u, v, w in flights:
            if dist[u] + w < tmp[v]: tmp[v] = dist[u] + w
        dist = tmp
    return -1 if dist[dst] == float('inf') else dist[dst]
# find_cheapest_price(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1) -> 700

Dry run

On the example, with k = 1 (two rounds):

dist[3] = 700. The route 2 → 3 (which would give 400) needs dist[2], but in round 1 the code reads dist[2] = inf from the snapshot, so it can’t be chained in. With k = 2 there’d be a third round and the answer would drop to 400.

Complexity

• Time: O(K·E). k + 1 rounds, each scanning every flight once.
• Space: O(V) for dist and its copy.

Edge cases and pitfalls

• No route within the limit returns -1, e.g. a single flight 0 → 1 when dst = 2.
• k = 0 means a direct flight only. With [[0,1,100],[1,2,100],[0,2,500]], k = 0 gives 500 and k = 1 gives 200.
• Updating in place (no snapshot) lets one round use several edges and returns routes with too many stops.
• Running k rounds instead of k + 1. Stops are the cities between src and dst, so k stops means k + 1 flights.
• src == dst returns 0 from the start, since dist[src] = 0 never gets worse.

Related problems

• Network Delay Time (LeetCode 743): shortest paths with no stop limit, where Dijkstra is the right tool.
• Find the City With the Smallest Number of Neighbors (LeetCode 1334): all-pairs shortest paths with a distance threshold.
• Path With Minimum Effort (LeetCode 1631): a shortest-path variant where Dijkstra’s state is a grid cell.