The problem. There are n cities, 0 to n - 1, and one-way flights[i] = [from, to, price]. Find the cheapest price from src to dst using at most `k` stops — that is, at most k + 1 flights. Return -1 if no such route exists.
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)
k = 2 -> 400 (0 -> 1 -> 2 -> 3)
k = 0 -> -1 (no direct flight from 0 to 3)Without the limit, this is Dijkstra. With it, Dijkstra's key promise breaks: Dijkstra settles a city at its cheapest price and never looks back — but the cheapest way into a city may use too many flights, while a pricier way with fewer flights is the one that can still reach dst in time. In the picture, city 2 is cheapest via 1 (200), but a route through 2 then needs 2 stops.
Bellman-Ford handles limits naturally because it counts edges. Round 1 finds the cheapest price to every city using one flight; round 2, using at most two; and so on. Run exactly k + 1 rounds and read off dst. One detail makes it exact: during a round, relax from the previous round's prices (a copy), otherwise a single round could chain two flights.
Anytime a path is limited by a count — stops, fuel, discounts, walls you may break — the trick is the same: make the count part of the state (or the round number), so routes with different counts are kept apart.
A DFS tries every sequence of at most k + 1 flights from src, remembering the cheapest that ends at dst. Stop following a route once it already costs as much as the best one.
function findCheapestPrice(n, flights, src, dst, k) { const adj = Array.from({ length: n }, () => []); for (const [u, v, price] of flights) adj[u].push([v, price]); let best = Infinity; const fly = (city, spent, flightsLeft) => { if (spent >= best) return; // already no cheaper than the best route if (city === dst) { best = spent; return; } if (flightsLeft === 0) return; for (const [next, price] of adj[city]) fly(next, spent + price, flightsLeft - 1); }; fly(src, 0, k + 1); // k stops = at most k + 1 flights return best === Infinity ? -1 : best;}Time O(dᵏ⁺¹), space O(k). d is the most flights leaving one city: each level of the search can branch d ways, k + 1 levels deep. Fine for tiny k, hopeless for k = 100.
Keep cost[city], the cheapest price found so far. Each round copies it into next, relaxes every flight from cost into next, and then makes next the new cost. After round i, cost is exact for routes of at most i flights.
Each round allows one more flight. Compare k = 1 with k = 2 on the same map.
function findCheapestPrice(n, flights, src, dst, k) { let cost = new Array(n).fill(Infinity); cost[src] = 0; for (let round = 0; round <= k; round++) { // k stops = at most k + 1 flights const next = [...cost]; // relax from LAST round's prices only for (const [u, v, price] of flights) { if (cost[u] + price < next[v]) next[v] = cost[u] + price; } cost = next; // now: cheapest using at most round + 1 flights } return cost[dst] === Infinity ? -1 : cost[dst];}Time O(k · E), space O(n). k + 1 rounds, each reading all E flights once, plus a copy of the n prices per round.
Dijkstra can work too, if the state includes how many flights were used. Pop the cheapest [cost, city, used]. The first time dst comes out, that's the answer. Otherwise expand the city — but only if this pop used fewer flights than any earlier pop of the same city: an earlier pop was cheaper, so a later one is only useful if it has flights to spare.
function findCheapestPrice(n, flights, src, dst, k) { const adj = Array.from({ length: n }, () => []); for (const [u, v, price] of flights) adj[u].push([v, price]); const fewest = new Array(n).fill(Infinity); // fewest flights of any earlier pop of each city const heap = new Heap((a, b) => a[0] - b[0]); // [cost, city, flights used], cheapest first heap.push([0, src, 0]); while (heap.size() > 0) { const [cost, city, used] = heap.pop(); if (city === dst) return cost; // the cheapest route within the limit if (used >= fewest[city] || used === k + 1) continue; // dominated, or out of flights fewest[city] = used; for (const [next, price] of adj[city]) heap.push([cost + price, next, used + 1]); } return -1;}Time O(k · E · log(k · E)), space O(k · E). Each city can be expanded up to k + 1 times, each time with strictly fewer flights, so the heap holds at most about (k + 1) · E entries.
Bellman-Ford is the cleanest answer here: a few lines, no heap, and the limit is simply the number of rounds. The Dijkstra version is worth knowing for problems where the count isn't a small number of rounds.