Cheapest Flights Within K Stops: Bounded Bellman-Ford

You need to fly from one city to another, and you want the cheapest ticket. The catch: you can only take a limited number of connecting flights. That is LeetCode 787: Cheapest Flights Within K Stops, and it is one of the best problems for learning how to adapt a classic shortest path algorithm to work with constraints.

Given n cities, a list of flights [from, to, price], a source city src, a destination city dst, and an integer k representing the maximum number of stops, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Why this problem matters

This problem sits at the intersection of graph algorithms and dynamic programming. On the surface it looks like a standard shortest path problem, but the stop limit changes everything. You cannot simply run Dijkstra's and call it done, because Dijkstra's greedy approach does not naturally respect a hop constraint. A path that is globally cheapest might use too many stops.

The problem teaches you a critical skill: modifying a well-known algorithm to handle additional constraints. In interviews, you will frequently encounter problems that are "almost" a textbook algorithm but require one twist. Knowing how to adapt Bellman-Ford to a bounded number of iterations is exactly that kind of twist.

The approach

The key insight is that Bellman-Ford naturally supports bounding the number of edges in a path. In standard Bellman-Ford, after i iterations of relaxing all edges, you have the shortest paths using at most i edges. Since "at most k stops" means "at most k + 1 edges" (the source does not count as a stop), you run exactly k + 1 iterations.

There is one important detail: you must use a copy of the distance array from the previous round when relaxing edges. If you update distances in place, a node relaxed early in the current round could cascade into later relaxations within the same round, effectively allowing more stops than intended.

Here is the plan:

1. Initialize a prices array: set prices[src] = 0 and everything else to infinity
2. Run k + 1 rounds: in each round, make a copy of the current prices array, then relax every edge using the copied values
3. Relax an edge: for flight [u, v, w], if prev[u] + w is less than prices[v], update prices[v]
4. Return the result: after all rounds, prices[dst] is the answer. If it is still infinity, return -1

Clean solution

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):
        prev = prices[:]
        for u, v, w in flights:
            if prev[u] + w < prices[v]:
                prices[v] = prev[u] + w

    return prices[dst] if prices[dst] != float("inf") else -1

Step-by-step walkthrough

Let's trace through the modified Bellman-Ford on our example graph with 5 cities, src = 0, dst = 4, and k = 1 (at most 1 stop, so 2 rounds of relaxation).

The critical observation is in round 2. When we relax edge 2 -> 4, we use prev[2] = 500 (the value from round 1), not the updated value of 200 that node 2 received earlier in round 2 from relaxing 1 -> 2. This ensures that the path to node 4 uses at most 2 edges (1 stop), going through the direct 0 -> 2 -> 4 route at cost 700.

If we had used the in-place updated value of 200 for node 2, we would have gotten prices[4] = 400 (the path 0 -> 1 -> 2 -> 4), which uses 2 stops and violates the k = 1 constraint.

Complexity analysis

The Bellman-Ford approach runs k + 1 iterations, each scanning all E flights. Space is O(V) for the prices array plus O(V) for the copy, so O(V) total. This makes it both simple and efficient.

The building blocks

Modified Bellman-Ford with bounded iterations

Standard Bellman-Ford runs V-1 iterations to find shortest paths in a graph (even with negative edges). By limiting it to k + 1 iterations, you enforce a constraint on the number of edges in the path. The key modification is copying the distance array before each round so that updates within one round do not cascade.

This pattern appears whenever you need shortest paths with a hop limit. It also connects to dynamic programming: prices[v] after round i is the minimum cost to reach v using at most i edges. Each round builds on the previous one, which is the hallmark of DP.

Edge relaxation

Relaxation is the core operation in both Bellman-Ford and Dijkstra's. For an edge (u, v, w), you check whether the path through u offers a cheaper route to v: if dist[u] + w is less than dist[v], update dist[v]. The difference here is that you read from a snapshot of the previous round (prev[u]) rather than the live array.

Copy-before-update pattern

In many DP and graph problems, you need to prevent the current round's updates from affecting other calculations in the same round. The solution is to work from a frozen copy of the previous state. You will see this pattern in problems like the game of life, multi-source BFS on grids, and anywhere layer-by-layer processing is required.

Edge cases to watch for

• No path exists: If dst is unreachable from src within k stops, prices[dst] stays at infinity. Return -1.
• Direct flight available: If there is a direct flight from src to dst, it gets picked up in round 1 (0 stops). The algorithm handles this naturally.
• k = 0: Zero stops means only a direct flight is allowed. One round of relaxation checks all edges, and only the direct src -> dst edge (if it exists) will update prices[dst].
• Multiple paths with same cost: The algorithm naturally keeps the minimum. No special handling needed.
• Large k values: If k is larger than n - 2, the constraint is effectively unbounded. The algorithm still works correctly, just running extra iterations that produce no changes.

From understanding to recall

You now understand why the copy step matters and how bounding the iterations enforces the stop constraint. But implementing this under interview pressure requires more than understanding. You need to remember three things: initialize the prices array, copy before each round, and loop k + 1 times. That is only six lines of code, but getting them right on the first try takes practice.

Spaced repetition helps you internalize these details. You write the solution from scratch, check it, and revisit it at increasing intervals. After a few rounds, the Bellman-Ford template with the copy step becomes automatic. When a bounded shortest path problem appears in your interview, you write it without hesitation.

Related posts

• Network Delay Time - Classic shortest path with Dijkstra, same graph relaxation idea
• Course Schedule - Graph traversal and topological ordering
• Coin Change - DP with bounded iterations, similar structure to bounded Bellman-Ford