Data Structures & Algorithms · Graphs

Cheapest Flights Within K Stops: BFS With State, Explained

Q: What does "k stops" actually mean — is it the number of flights?

No. k counts intermediate cities (layovers), so a trip with k stops uses k + 1 flights. A direct flight from source to destination has 0 stops. The algorithm encodes this by seeding the source at stops = 0 and refusing to expand any state where stops > k, which caps every explored route at k + 1 edges.

Q: Why is this called a Bellman-Ford approach if it uses a queue?

Bellman-Ford's core operation is relaxation: repeatedly checking whether a known edge gives a cheaper path and updating a tentative-cost array if so. This solution does exactly that with if (newPrice < minPrice[neighbor]), and it bounds the number of relaxation rounds by the stop limit — Bellman-Ford naturally caps path length at the iteration count. The BFS queue is just the mechanism for spreading those relaxations outward level by level instead of scanning the full edge list each round.

Q: What is the time and space complexity of the optimal solution?

Time is O(k · E), where E is the number of flights: each of the k + 1 stop-levels can relax every edge at most once, since a path only re-enters the queue when it improves a city's best cost. Space is O(n + k · E) — O(n) for the minPrice array, O(E) for the adjacency list, and up to O(k · E) for in-flight queue states. This is a decisive improvement over the exponential O(b^(k+1)) of naive DFS.

Solve Cheapest Flights Within K Stops with a level-bounded BFS that carries stop count as state — intuition, JavaScript code, a worked trace, and complexity.

July 17, 20268 min readBy Bhavesh Singh

graphsbfsbellman-ford / bfsshortest pathweighted graphleetcode medium

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the Cheapest Flights Within K Stops visualizer

Plain shortest-path algorithms answer "what's the cheapest way to get there?" Cheapest Flights Within K Stops adds one word that breaks them: "...using at most K stops?" Dijkstra will happily hand you a 5-hop bargain when you're only allowed 1 layover.

The fix is to stop treating each city as a single node and start treating (city, stops-used) as the thing you're exploring. Once stop count rides along as part of the state, a breadth-first sweep that relaxes prices — a level-bounded cousin of Bellman-Ford — finds the answer cleanly.

This is one of the most common ways interviewers test whether you understand why a shortest-path algorithm works, not just how to call one.

The problem

You're given n cities numbered 0 to n-1 and a list flights where each entry [from, to, price] is a one-way flight. Given a source src, a destination dst, and an integer k, return the cheapest total price to fly from src to dst using at most k stops. If it can't be done within k stops, return -1.

The one detail that trips everyone: k stops means k intermediate cities, which is k + 1 flights. A direct flight uses 0 stops.

text

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

Route 0 -> 1 -> 3 costs 100 + 600 = 700 and uses 1 stop (city 1).
The route 0 -> 1 -> 2 -> 3 is cheaper at 400, but it uses 2 stops — over the limit.

That second route is the whole point: the globally cheapest path is disqualified by the stop budget, so the algorithm has to reason about cost and stops together.

The brute force baseline

The direct approach is a depth-first search that tries every route, backing off once it has spent k + 1 flights.

javascript

function findCheapestPrice(n, flights, src, dst, k) {
  const graph = Array.from({ length: n }, () => []);
  for (const [from, to, price] of flights) graph[from].push([to, price]);

  let best = Infinity;

  function dfs(city, cost, stopsLeft) {
    if (city === dst) { best = Math.min(best, cost); return; }
    if (stopsLeft < 0) return;
    for (const [next, price] of graph[city]) {
      dfs(next, cost + price, stopsLeft - 1);
    }
  }

  dfs(src, 0, k + 1);
  return best === Infinity ? -1 : best;
}

It's correct, but it re-walks overlapping routes endlessly. With branching factor b and depth k + 1, the search explores up to O(b^(k+1)) paths — exponential in the stop budget. On a dense graph with even a modest k, that blows up. We need to stop re-deriving the cost to reach a city we've already priced.

The key insight: carry stops as state

Ordinary Dijkstra fails here because it commits to the cheapest way to reach each city and never reconsiders. But the cheapest unrestricted route to a city might use too many stops, while a slightly pricier route with fewer stops is the one that actually reaches the destination in time.

The reframe: explore breadth-first by number of stops. Push trip states [city, cost, stops] onto a queue and expand them one layer at a time. Because BFS naturally processes all 0-stop paths, then all 1-stop paths, and so on, the number of stops used is baked into how far you've traveled from the source.

Keep a minPrice[] array — the best cost seen so far for each city — and only enqueue a neighbor when you've found a cheaper way to reach it. That relaxation is the Bellman-Ford idea: repeatedly improve tentative costs. Bounding the traversal by stops <= k is what turns unbounded shortest-path into shortest-path-within-a-hop-budget.

The optimal solution

This is the exact algorithm the visualizer steps through — a BFS queue of [city, cost, stops] triples, guarded by the stop limit, relaxing minPrice as it spreads outward.

javascript

var findCheapestPrice = function(n, flights, src, dst, k) {
    let graph = Array.from({ length: n }, () => []);
    for (let [from, to, price] of flights) {
        graph[from].push([to, price]);
    }

    let minPrice = new Array(n).fill(Infinity);
    minPrice[src] = 0;

    let q = [[src, 0, 0]];
    while (q.length) {
        let [curr, currPrice, stops] = q.shift();
        if (stops > k) continue;
        for (let [neighbor, neighborPrice] of graph[curr]) {
            let newPrice = currPrice + neighborPrice;
            if (newPrice < minPrice[neighbor]) {
                minPrice[neighbor] = newPrice;
                q.push([neighbor, newPrice, stops + 1]);
            }
        }
    }
    return minPrice[dst] === Infinity ? -1 : minPrice[dst];
};

Three moving parts carry the whole solution:

minPrice[] — the cheapest cost found so far to each city. It starts at Infinity everywhere except minPrice[src] = 0.
The queue — each entry is a full trip snapshot [city, cost, stops], so a city can appear multiple times reached via different routes.
if (stops > k) continue — the depth guard. Once a dequeued path has already used more than k stops, we drop it before expanding, so no route ever explores past k + 1 flights.

The relaxation if (newPrice < minPrice[neighbor]) does double duty: it records improvements and prunes. If a path can't beat the best known cost to a city, there's no reason to enqueue it.

Walkthrough

Tracing the example 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. The adjacency list is 0 → [[1,100]], 1 → [[2,100],[3,600]], 2 → [[0,100],[3,200]], 3 → [].

Step	Dequeued `[curr, cost, stops]`	Guard `stops > 1`?	Edges relaxed	minPrice after	Queue after
Init	—	—	—	`[0, ∞, ∞, ∞]`	`[[0,0,0]]`
1	`[0, 0, 0]`	no	`0→1`: 0+100=100 < ∞ ✓	`[0, 100, ∞, ∞]`	`[[1,100,1]]`
2	`[1, 100, 1]`	no	`1→2`: 200 < ∞ ✓; `1→3`: 700 < ∞ ✓	`[0, 100, 200, 700]`	`[[2,200,2], [3,700,2]]`
3	`[2, 200, 2]`	yes → skip	none	`[0, 100, 200, 700]`	`[[3,700,2]]`
4	`[3, 700, 2]`	yes → skip	none	`[0, 100, 200, 700]`	`[]`

Step 3 is the decisive one. City 2 was reachable at cost 200, and from there 2→3 would cost only 400 total — cheaper than 700. But that path sits at 2 stops, over the k = 1 budget, so the guard discards it before it can relax minPrice[3]. That's exactly why the answer is 700 and not the globally cheapest 400. The queue drains, and minPrice[3] = 700 is returned.

Complexity

Let E be the number of flights (edges) and n the number of cities.

Metric	Value	Why
Time	O(k · E)	Each of the `k + 1` stop-levels can relax every edge once, so the queue processes on the order of `k · E` states
Space	O(n + k · E)	`minPrice` is `O(n)`; the graph is `O(E)`; the queue can hold up to `O(k · E)` in-flight states

The exponential DFS collapses to polynomial because minPrice prevents re-enqueuing any path that can't improve a city's best cost — the same relaxation bound that makes Bellman-Ford O(V·E).

Common mistakes

Confusing stops with edges. k stops equals k + 1 flights. Seeding the source at stops = 0 and skipping when stops > k is what encodes this — off-by-one here silently returns wrong answers.
Reaching for plain Dijkstra. Popping the globally cheapest city and stopping at dst ignores the stop budget entirely; it'll return the 400 route in the example. Stops must be part of the state.
Using a single visited set. A city may need to be re-processed when it's reached later at a lower cost. Gate re-entry on newPrice < minPrice[neighbor], never on "have I touched this city before."
Checking the stop limit only when enqueuing. The canonical code enqueues freely and guards on dequeue (if (stops > k) continue). That keeps the head of a stops == k path able to explore its last legal layer of flights before the over-budget children get discarded.
Forgetting the unreachable case. If minPrice[dst] is still Infinity after the queue drains, the destination wasn't reachable within k stops — return -1, don't return Infinity.

Where this pattern shows up next

Modeling a problem as a graph and sweeping it breadth-first is one of the most transferable skills in interviews. These build on the same foundation:

Find if Path Exists in Graph — the unweighted, no-budget version: does any route connect two nodes?
All Paths From Source to Target — enumerate every route in a DAG, the same exhaustive search the brute-force baseline here does.
Clone Graph — BFS/DFS traversal where the trick is tracking visited nodes to handle cycles.
Max Area of Island — grid-as-graph flood fill, the gentlest introduction to exploring connected components.

You can also step through Cheapest Flights Within K Stops interactively to watch the queue fill, the stop guard fire, and minPrice relax one flight at a time.

FAQ

Why doesn't Dijkstra's algorithm work for Cheapest Flights Within K Stops?

Dijkstra finalizes the cheapest cost to each city and never revisits it, which is correct only when there's no constraint beyond cost. Here the cheapest overall route may use more than k stops, disqualifying it, while a pricier route with fewer stops is the valid answer. Because Dijkstra would lock in the disqualified cost, it can't respect the stop budget unless you extend the state to include stops — at which point you're doing the level-bounded BFS or Bellman-Ford shown here.

What does "k stops" actually mean — is it the number of flights?

No. k counts intermediate cities (layovers), so a trip with k stops uses k + 1 flights. A direct flight from source to destination has 0 stops. The algorithm encodes this by seeding the source at stops = 0 and refusing to expand any state where stops > k, which caps every explored route at k + 1 edges.

Why is this called a Bellman-Ford approach if it uses a queue?

Bellman-Ford's core operation is relaxation: repeatedly checking whether a known edge gives a cheaper path and updating a tentative-cost array if so. This solution does exactly that with if (newPrice < minPrice[neighbor]), and it bounds the number of relaxation rounds by the stop limit — Bellman-Ford naturally caps path length at the iteration count. The BFS queue is just the mechanism for spreading those relaxations outward level by level instead of scanning the full edge list each round.

What is the time and space complexity of the optimal solution?

Time is O(k · E), where E is the number of flights: each of the k + 1 stop-levels can relax every edge at most once, since a path only re-enters the queue when it improves a city's best cost. Space is O(n + k · E) — O(n) for the minPrice array, O(E) for the adjacency list, and up to O(k · E) for in-flight queue states. This is a decisive improvement over the exponential O(b^(k+1)) of naive DFS.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the Cheapest Flights Within K Stops visualizer

The problem#

The brute force baseline#

The key insight: carry stops as state#

The optimal solution#

Walkthrough#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

Why doesn't Dijkstra's algorithm work for Cheapest Flights Within K Stops?#

What does "k stops" actually mean — is it the number of flights?#

Why is this called a Bellman-Ford approach if it uses a queue?#

What is the time and space complexity of the optimal solution?#

Related articles