787. Cheapest Flights Within K Stops

mediumAsked at Cisco

Cheapest Flights at Cisco is the constrained-shortest-path problem they ask after Network Delay Time. Adding a hop-limit forces you to either modify Dijkstra to track stops or pivot to Bellman-Ford bounded to K+1 relaxations. The interviewer is checking whether you know Dijkstra-with-state-augmentation isn't always the right tool.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Cisco loops.

Glassdoor (2026-Q1)— Cisco Network Software Engineer reports list this as the canonical 'shortest path with hop limit' problem.
Blind (2025-11)— Cisco SDE-II interview write-up reports both Bellman-Ford and Dijkstra-with-stops accepted.

Problem

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. 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 <= fromi, toi < n
fromi != toi
1 <= pricei <= 10^4
There will not be any multiple flights between two cities.
0 <= src, dst, k < n
src != dst

Examples

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

Explanation: Optimal path 0 -> 1 -> 3 costs 700. Cheaper 0 -> 1 -> 2 -> 3 = 400 is blocked because it has 2 stops > k=1.

Example 2

Input

n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output

Explanation: With 0 stops, must take direct flight 0 -> 2.

Approaches

1. Brute-force DFS with depth limit

DFS from src tracking (current node, cost, stops). Prune when stops > k or cost > best.

Time: O(n^k)
Space: O(n + k)

function findCheapestPriceBrute(n, flights, src, dst, k) {
  const graph = Array.from({ length: n }, () => []);
  for (const [f, t, p] of flights) graph[f].push([t, p]);
  let best = Infinity;
  function dfs(node, cost, stops) {
    if (cost >= best) return;
    if (node === dst) { best = cost; return; }
    if (stops > k) return;
    for (const [next, price] of graph[node]) {
      dfs(next, cost + price, stops + 1);
    }
  }
  dfs(src, 0, 0);
  return best === Infinity ? -1 : best;
}

Tradeoff: Exponential worst-case but pruning makes it fast on small inputs. The 'best' pruning is critical — without it, n=100 and k=99 explodes. Bring this up only to show you understand the brute force before optimizing.

2. Bellman-Ford bounded to K+1 relaxations (optimal)

Classic Bellman-Ford does V-1 rounds of edge relaxation. Cap rounds at K+1 (K stops = K+1 edges) and you've solved the problem. Copy the dist array each round so updates from round i don't affect round i.

Time: O(K * E)
Space: O(V)

function findCheapestPrice(n, flights, src, dst, k) {
  let dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i <= k; i++) {
    const next = dist.slice();
    for (const [u, v, w] of flights) {
      if (dist[u] === Infinity) continue;
      if (dist[u] + w < next[v]) next[v] = dist[u] + w;
    }
    dist = next;
  }
  return dist[dst] === Infinity ? -1 : dist[dst];
}

Tradeoff: Each round adds one more edge to the considered paths. After K+1 rounds, dist[v] = cheapest path with at most K+1 edges = K stops. The slice() per round is what makes it correct — Bellman-Ford's textbook 'two-array' variant.

3. Dijkstra with state augmentation

Push (cost, node, stops_remaining) into a min-heap. Only push neighbors when stops_remaining > 0.

Time: O((V+E) * K log V)
Space: O(V * K)

function findCheapestPriceDijkstra(n, flights, src, dst, k) {
  const graph = Array.from({ length: n }, () => []);
  for (const [f, t, p] of flights) graph[f].push([t, p]);
  const heap = [[0, src, k + 1]];
  const visited = new Map();
  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [cost, node, stops] = heap.shift();
    if (node === dst) return cost;
    if (stops === 0) continue;
    const key = node;
    if (visited.has(key) && visited.get(key) >= stops) continue;
    visited.set(key, stops);
    for (const [next, price] of graph[node]) {
      heap.push([cost + price, next, stops - 1]);
    }
  }
  return -1;
}

Tradeoff: Subtle: regular Dijkstra is INCORRECT here because the cheapest-so-far node might require too many hops; a more-expensive-but-fewer-hops node might still be on the optimal solution. Augmenting state with stops_remaining fixes this but bloats the search space.

Cisco-specific tips

Cisco interviewers grade this on whether you can articulate WHY plain Dijkstra fails. Say it explicitly: 'Plain Dijkstra is greedy on cost, so once it finalizes a node it never reconsiders. But here a cheaper-but-too-many-hops path can block a more-expensive-but-allowed-by-K path.' Then pivot to Bellman-Ford with the K-round bound — it's the cleaner code AND the more correct framing.

Common mistakes

Forgetting to slice() the dist array each Bellman-Ford round — without that, updates within a round bleed into other paths and let you take more than K+1 edges.
Confusing K stops with K edges — K stops = K+1 edges (your trip touches K+2 nodes).
Applying plain Dijkstra and accepting the first-time-you-pop-dst as correct — wrong because that path may exceed K stops.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

What if we need the PATH itself, not just the cost? (Track predecessor + stops per state.)
Multi-criteria: minimize cost AND number of stops as a Pareto front.
Bidirectional Dijkstra for sparse graphs.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is Bellman-Ford the cleaner solution here?

Because the constraint maps perfectly: K stops = K+1 edges = K+1 rounds of edge relaxation. The 'slice the array per round' invariant gives you exactly that. The Dijkstra variant has to carry stops_remaining as part of the state, which bloats both the code and the search space.

Why does plain Dijkstra fail?

Dijkstra finalizes a node the first time it pops, based on minimum cost. But here, a path could be cheap and use too many hops; a more expensive path with fewer hops might be the only legal one. Plain Dijkstra would lock in the cheap-but-illegal path. State augmentation (cost, node, stops) fixes it but you're really just paying for the constraint.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Cheapest Flights Within K Stops and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →