K stops means K + 1 flights
A stop is an intermediate city, so a route with K stops takes K + 1 flights. Settle this out loud before writing anything. An off-by-one here gives a wrong answer that looks right on most samples.
Take four cities. Flights run 0 → 1 for 100, 1 → 2 for 100, 2 → 0 for 100, 1 → 3 for 600 and 2 → 3 for 200. You fly from 0 to 3 with at most one stop. The cheapest route overall is 0 → 1 → 2 → 3 for 400, but it has two stops. The best route that is allowed is 0 → 1 → 3 for 700. Plain Dijkstra returns 400.
Why Dijkstra's settling rule breaks
Dijkstra's correctness, covered on the negative-edge page, rests on one claim. Once a city is popped at cost d, no later route reaches it more cheaply, so d is all you need to know about that city.
With a stop budget, cost alone no longer describes a partial route. A route arriving at a city has a price and a number of flights used, and neither dominates the other. A cheap arrival with no stops left is useless for going further. A dearer arrival with stops to spare may be the only way to finish. Dijkstra's rule keeps one number per city, so it has to discard one of them, and sometimes it discards the one you needed.
The candidate who adds a counter and keeps a visited flag per city walks straight into this. Take flights 0 → 1 for 1, 1 → 2 for 1, 0 → 2 for 5 and 2 → 3 for 1, from 0 to 3 with at most one stop.
- Pop 0. Push city 1 at cost 1 and city 2 at cost 5, each after one flight.
- Pop city 1 at cost 1. Push city 2 at cost 2, after two flights.
- Pop city 2 at cost 2 and mark it visited. Both allowed flights are used, so 2 → 3 cannot be taken.
- Pop city 2 at cost 5. It is already visited, so it is skipped.
The heap empties and the answer comes back as "unreachable". The real answer is 0 → 2 → 3 for 6, which uses one stop.
Bellman-Ford with a round limit
Bellman-Ford relaxes every edge once per round. If each round reads only the distances from the end of the previous round, then after round i every distance is the cheapest price using at most i flights. Run K + 1 rounds and read off the destination.
int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
final int INF = Integer.MAX_VALUE;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int round = 0; round <= k; round++) {
int[] next = dist.clone();
for (int[] f : flights) {
int from = f[0], to = f[1], price = f[2];
if (dist[from] != INF && dist[from] + price < next[to]) {
next[to] = dist[from] + price;
}
}
dist = next;
}
return dist[dst] == INF ? -1 : dist[dst];
}
The clone is the line that matters. Relax in place and one round can chain several flights, because an update made early in the round is read later in the same round. Take flights 0 → 1 for 100, 1 → 2 for 100 and 0 → 2 for 500, listed in that order, with K = 0. In-place relaxation sets city 1 to 100 and then city 2 to 200 in the same round, which is a one-stop route. The correct direct-only answer is 500.
Time is O((K + 1) × E) and space is O(n). That is dynamic programming over (flights used, city), which is why the copy is not an optimisation detail but the definition of the state. Use long if fares can be large enough for a path of K + 1 of them to overflow an int.
Dijkstra on an expanded state
Dijkstra itself works if each heap entry carries the number of flights used, and best costs are kept per (city, flights used) pair rather than per city. Pop entries in cost order and skip one only if that exact pair already has a cheaper cost. The first time the destination is popped, its cost is the answer, because every remaining entry costs at least as much. An entry that has used K + 1 flights is not expanded further.
There are n × (K + 2) states, and each relaxes its outgoing flights at most once, so the heap sees at most about E × (K + 1) pushes, each with a logarithmic cost. It can finish well before Bellman-Ford, because it stops at the first pop of the destination. Bellman-Ford is shorter to write and harder to get wrong under time pressure, and that is a fair reason to choose it in an interview.
The round-limited version also handles negative fares, which Dijkstra cannot. With unbounded path length, a negative cycle makes the cheapest route undefined. With a hard cap on flights, a route can loop only so many times, so every answer is finite and K + 1 rounds still compute it.
A stop limit turns "cheapest route to this city" into "cheapest route to this city in i flights". Any version that keeps one number per city has lost the information the answer depends on.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).