4.21.6 — Cheapest Flights Within K Stops

LeetCode 787 · Medium

The problem

Find the cheapest route from src to dst using at most k stops — that is, at most k + 1 flights. Return -1 if there is none.

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

→ 700     (0 → 1 → 3, one stop)

The route 0 → 1 → 2 → 3 costs only 500, but it uses two stops and is not allowed.

Why Dijkstra gives the wrong answer

This is the point of the problem, so it is worth being precise.

Dijkstra finalises a node the first time it pops, on the grounds that no cheaper route can exist. With a hop limit that reasoning collapses:

A cheap route to a node may use too many hops to be extended further, while a more expensive route with fewer hops is the one you need.

In the example, Dijkstra reaches node 2 cheaply via 0 → 1 → 2 for 200, then finalises it. But that route has already used two flights, so continuing to 3 needs a third and exceeds the limit. Meanwhile node 1 at cost 100 with one flight used is the route that actually works.

The lesson generalises: Dijkstra's finalisation is only valid when cost is the only thing that matters. Add a second constraint — hop count, fuel, time window — and a node's "best" state is no longer a single number, so a single finalised distance is not enough.

Two ways out.

Solution 1 — Bellman-Ford, and it fits perfectly

Bellman-Ford relaxes every edge, repeatedly. After i rounds, it knows the cheapest route using at most i edges.

That is exactly the constraint here. Run it k + 1 times and you have the cheapest route using at most k + 1 flights. The hop limit, which broke Dijkstra, is the very thing Bellman-Ford counts.

Python

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k) -> int:
        INF = float('inf')
        cost = [INF] * n
        cost[src] = 0

        for _ in range(k + 1):                 # at most k+1 flights
            snapshot = cost[:]                 # ← the critical line
            for u, v, w in flights:
                if snapshot[u] + w < cost[v]:
                    cost[v] = snapshot[u] + w

        return cost[dst] if cost[dst] != INF else -1

TypeScript

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
  const INF = Infinity;
  let cost = new Array(n).fill(INF);
  cost[src] = 0;

  for (let round = 0; round <= k; round++) {
    const snapshot = [...cost];
    for (const [u, v, w] of flights) {
      if (snapshot[u] + w < cost[v]) cost[v] = snapshot[u] + w;
    }
  }

  return cost[dst] === INF ? -1 : cost[dst];
}

snapshot = cost[:] is the line the whole solution depends on.

Without it, a single round could chain several flights: relaxing 0 → 1 updates cost[1], and then relaxing 1 → 2 in the same round uses that fresh value, so two flights were taken in one round. The hop count becomes meaningless.

Copying the array first means every relaxation in a round reads the state from the end of the previous round, so exactly one flight is added per round. That is the difference between "at most i edges" and "any number of edges", and it is why standard Bellman-Ford — which does not snapshot — cannot answer this question directly.

O(k \times E) time, O(n) space. Short, and easy to defend.

Solution 2 — BFS by levels

Walk outward one flight at a time, keeping the cheapest known cost to each node.

from collections import deque

def findCheapestPrice(self, n, flights, src, dst, k):
    adj = defaultdict(list)
    for u, v, w in flights:
        adj[u].append((v, w))

    best = [float('inf')] * n
    best[src] = 0
    queue = deque([(src, 0)])
    stops = 0

    while queue and stops <= k:
        for _ in range(len(queue)):            # one level = one flight
            node, cost = queue.popleft()
            for nei, w in adj[node]:
                if cost + w < best[nei]:       # only continue if we improved
                    best[nei] = cost + w
                    queue.append((nei, cost + w))
        stops += 1

    return best[dst] if best[dst] != float('inf') else -1

The level structure counts the flights, and pruning on cost + w < best[nei] stops the queue exploding. It is the same shape as every level-order BFS in this book.

Solution 3 — Dijkstra with the state extended

Dijkstra can be rescued by changing what a "node" means. Make the state (node, flights used) rather than just node, and track the best cost for each combination.

heap = [(0, src, 0)]        # (cost, node, flights used)

Now finalising is safe again, because two routes to the same airport with different flight counts are genuinely different states.

O(E \cdot k \log(V \cdot k)) — more code and more memory than Bellman-Ford. But the idea behind it is the important one:

When a second constraint breaks a graph algorithm, put the constraint into the state.

That move fixes fuel limits, time windows, "at most two refuels", and a large family of DP-on-graph problems. It is the same idea as adding a dimension to a DP table in 4.24.

Which to write

Bellman-Ford. It is eight lines, the hop limit is native to it, and the snapshot is easy to explain. Mention the other two and say why you chose this one.

Complexity

O(k \times E) time, O(n) space.

Where this goes next

• Bellman-Ford in general — run it V − 1 rounds for shortest paths with negative weights. A further round that still improves something means a negative cycle, since no simple path has more than V − 1 edges. That is how negative cycles are detected.
• Path with Maximum Probability, Minimum Cost to Reach Destination in Time — the extended-state idea.
• Real routing — the distance-vector protocols behind RIP are Bellman-Ford, and their count-to-infinity problem is a direct consequence of it. Chapter 5.3.2.

What the interviewer will push on

"Why not Dijkstra?" A cheaper route may use too many hops. Give the concrete example from the problem statement.

"Why does Bellman-Ford fit?" After i rounds it knows the cheapest route using at most i edges, which is exactly the constraint.

"Why the snapshot?" Without it, one round can chain several flights and the hop count is meaningless. This is the question that separates people who understand the code from people who copied it.

"Could you still use Dijkstra?" Yes, with (node, flights used) as the state.

"How does Bellman-Ford detect a negative cycle?" An improvement on the V-th round.

One thing to volunteer: state the general rule. "A second constraint breaks Dijkstra's finalisation, so either count the constraint in rounds — Bellman-Ford — or fold it into the state." That sentence covers a whole family of problems.

Next: 4.22 is the chapter most people find hardest, so it is built from the ground up — what makes a problem dynamic programming rather than greedy, the five questions that produce the recurrence, and the four forms the same solution can take.