Cheapest Flights Within K Stops — Bellman-Ford with a Twist

Problem Statement#

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, 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.

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= from_i, to_i < n, from_i != to_i
• 1 <= price_i <= 10^4
• There will not be any multiple flights between two cities.
• 0 <= k <= n

Example 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
Explanation: 0→1→3 costs 700. 0→1→2→3 uses 2 stops (exceeds k=1), so it is not allowed.

Example 2:

Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1
Output: 200
Explanation: 0→1→2 costs 200, which uses exactly 1 stop. Cheaper than the direct 0→2 at 500.

Example 3:

Input:  n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=0
Output: 500
Explanation: k=0 means no intermediate stops allowed. Only direct 0→2 at 500 is valid.

Why This Problem Matters#

This problem is the follow-up every interviewer asks right after Network Delay Time: "What if you add a constraint on the number of hops?" It forces you to realise that Dijkstra, which is purely distance-greedy, cannot handle a step-count constraint without augmenting the state — and that Bellman-Ford, which naturally relaxes edges in rounds, is the cleaner tool here.

Bellman-Ford is underrated in interviews. It is slower than Dijkstra for pure shortest-path work, but its round-by-round structure maps directly onto problems with layered constraints: at most k hops, at most k transactions (Best Time to Buy and Sell Stock with at most k transactions is Bellman-Ford in disguise), at most k edges.

The problem also appears in airline API design: given a flight graph with pricing, find the cheapest itinerary with at most one connection. Understanding the layered relaxation gives you a clean O(k * E) algorithm that is easy to explain and easy to code correctly under pressure.

The Core Insight#

With Dijkstra you greedily finalize the cheapest node. The issue is that taking a detour through an expensive node might later lead to a cheaper overall path, and if you have already finalized that detour node, Dijkstra cannot revisit it with a different hop count. The state space needs to be (city, hops_used), which makes Dijkstra workable but complex.

Bellman-Ford solves this naturally: in round i, it computes the cheapest cost to reach every city using at most i edges. After k+1 rounds (at most k stops = at most k+1 edges), dist[dst] holds the answer.

The critical implementation detail: use a copy of the distance array at the start of each round. If you update dist in-place during a round, you may chain updates within the same round — meaning a path that uses 3 edges in one round update — which violates the "at most 1 edge per round" invariant. Always copy dist at the round start and write updates to the copy.

Visual Dry Run#

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

k=1 stop means at most k+1=2 edges.

Initial: dist = [0, inf, inf, inf]

Round 1 (at most 1 edge), tmp starts as copy of dist:

• Edge (0,1,100): dist[0]=0, 0+100=100 < tmp[1]=inf → tmp[1]=100
• Edge (1,2,100): dist[1]=inf → skip
• Edge (2,0,100): dist[2]=inf → skip
• Edge (1,3,600): dist[1]=inf → skip
• Edge (2,3,200): dist[2]=inf → skip
• dist becomes [0, 100, inf, inf]

Round 2 (at most 2 edges), tmp starts as copy of dist:

• Edge (0,1,100): 0+100=100, not < tmp[1]=100 → no change
• Edge (1,2,100): dist[1]=100, 100+100=200 < inf → tmp[2]=200
• Edge (1,3,600): dist[1]=100, 100+600=700 < inf → tmp[3]=700
• Edge (2,3,200): dist[2]=inf → skip (using dist, not tmp!)
• dist becomes [0, 100, 200, 700]

Answer: dist[3] = 700

Common Mistakes#

1. Updating dist in-place during a round instead of using a copy. This is the single most common bug. If edge (0,1) updates dist[1] in round 1, and then edge (1,2) uses the already-updated dist[1] in the same round, you have effectively used 2 edges in one round. Always start the round with tmp = dist[:] and write all updates to tmp.

2. Running k rounds instead of k+1 rounds. k stops means k intermediate cities, which equals k+1 edges. If you run only k relaxation rounds, you allow at most k edges — one too few. The loop should run k+1 times.

3. Using Dijkstra without state augmentation. Plain Dijkstra minimizes total cost, ignoring the stop constraint. A path with 5 cheap hops might be selected over a path with 1 expensive hop, even when k=1. You need either Bellman-Ford or Dijkstra with state (city, stops_used).

4. Forgetting the early termination when dist[u] is infinity. If dist[u] is still infinity at the start of a round, relaxing edges from u produces inf + price, which in languages without native infinity arithmetic can overflow. Always guard with if dist[u] != float('inf') before computing dist[u] + price.

5. Confusing "stops" with "edges". The problem says "at most k stops." A stop is an intermediate city — not the source and not the destination. So src→A→dst has 1 stop and 2 edges. Always translate: k stops = k+1 edges = k+1 Bellman-Ford rounds.

6. Returning dist[dst] without converting infinity to -1. If dst is unreachable within k stops, dist[dst] stays at float('inf'). The problem expects -1. Always check: return dist[dst] if dist[dst] != float('inf') else -1.

Solutions#

Python#

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
        # dist[city] = cheapest cost to reach city from src with limited edges
        dist = [float('inf')] * n
        dist[src] = 0  # cost to reach source is 0
 
        # k stops = k+1 edges, so run k+1 relaxation rounds
        for _ in range(k + 1):
            # Snapshot dist before this round — prevents chaining updates within one round
            tmp = dist[:]
 
            for u, v, price in flights:
                # Only relax if u is reachable from src in the previous round
                if dist[u] != float('inf') and dist[u] + price < tmp[v]:
                    tmp[v] = dist[u] + price  # write to tmp, not dist
 
            dist = tmp  # commit this round's updates
 
        # If dst is unreachable within k+1 edges, return -1
        return dist[dst] if dist[dst] != float('inf') else -1

JavaScript#

var findCheapestPrice = function(n, flights, src, dst, k) {
    // dist[city] = cheapest known cost from src; initialize to Infinity
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0; // cost to reach source is 0
 
    // k stops = k+1 edges → run k+1 Bellman-Ford rounds
    for (let i = 0; i <= k; i++) {
        // Snapshot dist before this round to prevent within-round chaining
        const tmp = [...dist];
 
        for (const [u, v, price] of flights) {
            // Only relax if u was reachable in the previous round
            if (dist[u] !== Infinity && dist[u] + price < tmp[v]) {
                tmp[v] = dist[u] + price; // write update to tmp, not dist
            }
        }
 
        dist.splice(0, n, ...tmp); // commit round updates to dist
    }
 
    // Return -1 if dst is unreachable within k stops
    return dist[dst] === Infinity ? -1 : dist[dst];
};

Complexity Analysis#

Bellman-Ford is the recommended approach for this problem. With k up to 100 and E up to ~5000, the worst case is 500,000 edge relaxations — trivial for modern hardware.

Follow-up Questions#

Q: What if k is very large (essentially unlimited stops)? Run standard Bellman-Ford for V-1 rounds. If no negative cycle exists, this gives all-pairs shortest paths. With non-negative prices, Dijkstra is faster: O(E log V).

Q: Can this problem have negative price edges? The constraint says price >= 1, so no. But Bellman-Ford is naturally negative-edge-safe (it detects negative cycles after V rounds). Dijkstra would need modification.

Q: How do you reconstruct the actual route (not just the cost)? Maintain a prev[city] array. When you update tmp[v], also record prev[v] = u. After all rounds, trace back from dst to src using prev.

Q: What if we want exactly k stops, not at most k stops? Change the initialisation: dist_round[i][city] = cheapest cost using exactly i edges. At round i, only copy from round i-1. This is a layer-by-layer DP.

This Pattern Solves#

• LC 787 — Cheapest Flights Within K Stops (this problem)
• LC 743 — Network Delay Time (Dijkstra, no stop constraint)
• LC 1928 — Minimum Cost to Reach Destination in Time (DP + layered BFS)
• LC 123 — Best Time to Buy and Sell Stock III (Bellman-Ford layer logic)
• LC 188 — Best Time to Buy and Sell Stock IV (k-transaction DP)

Key Takeaways#

• Use Bellman-Ford with exactly k+1 rounds: k stops = k+1 edges traversed
• Copy the distance array before each round to prevent within-round chaining — this is the critical correctness requirement
• "k stops" in the problem means k intermediate nodes, so the path uses at most k+1 edges
• Guard relaxation with if dist[u] < infinity — do not propagate from unreachable nodes
• Time O(k * E), space O(V) — one round per edge layer; much simpler than modified Dijkstra
• Return -1 if dist[dst] is still infinity after k+1 rounds — the destination is unreachable within the constraint
• This round-based Bellman-Ford structure is the cleanest approach for "shortest path with at most k hops"