Cheapest Flights Within K Stops
Problem Statement
There are n cities labelled 0..n - 1 and a list of directed flights flights[i] = [from, to, price].
Given src, dst, and k, return the cheapest price from src to dst using at most k stops. A route with k stops uses at most k + 1 edges. Return -1 if no such route exists.
Input
The number of cities n, directed weighted edges flights, source src, destination dst, and maximum allowed stops k.
Output
An integer: the minimum feasible route cost from src to dst, or -1 if every route exceeds the stop limit or is disconnected.
Constraints
- •
1 <= n <= 100 - •
0 <= flights.length <= n * (n - 1) - •
flights[i].length == 3 - •
0 <= from, to < n - •
from != to - •
1 <= price <= 10000 - •
0 <= src, dst < n - •
src != dst - •
0 <= k < n
Examples
Example 1
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
700Example 2
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
200Example 3
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
500Learning Objectives
- Convert the stop limit into an edge limit: at most k stops means at most k + 1 flights.
- Use limited Bellman-Ford rounds to model paths with bounded edge counts.
- Understand why a clone of the distance array is required in each relaxation round.
- Model shortest path with state when cost alone is not enough; here the state is city plus edges used.
Intuition
This looks like a normal cheapest-path problem, but the stop constraint changes the state space. A route that is cheapest to reach an intermediate city may already have used too many flights, while a slightly more expensive prefix with fewer edges may still be the one that reaches the destination legally.
That is why naive Dijkstra keyed only by city is wrong. If you keep one best cost per city, you can discard a route that is more expensive so far but uses fewer stops, and that discarded route may be the only feasible way to finish.
The cleanest fix is limited Bellman-Ford. After one relaxation round, distances represent best costs using at most one edge. After two rounds, at most two edges. Therefore after k + 1 rounds, distances exactly match the stop constraint. The clone matters: within a single round, every update must be based on distances from the previous round, otherwise one round could chain multiple flights and silently violate the edge budget.
A second optimal framing is Dijkstra over expanded state: city + edges used. In that graph, the same city reached with different edge counts is treated as different state, so the algorithm never confuses cheap-but-too-long with feasible.
Common mistakes
- ×Running ordinary Dijkstra with one dist per city, which ignores the stop dimension and can prune the correct answer.
- ×Doing k relaxation rounds instead of k + 1. Stops are intermediate cities; edges are flights.
- ×Updating the Bellman-Ford distance array in place during a round, allowing paths with multiple new edges to appear in the same round.
- ×Treating flights as undirected; every flight is directed from source to destination.
- ×Returning a route that reaches dst cheaply but uses more than k stops.
Algorithm Explanation
Limited Bellman-Ford: keep dist as best costs using at most the number of edges processed so far. For each of k + 1 rounds, clone dist into next, relax every flight from the old dist into next, then replace dist with next. The clone enforces that one round adds at most one flight.
Priority queue over state: build an adjacency list and push states ordered by total cost. A state contains city and edges used. You may expand it only if edges used is less than k + 1. Track best[city][edgesUsed] so revisiting a city with a different edge count remains possible.
Use limited Bellman-Ford when you want the shortest, hardest-to-get-wrong solution. Use the stateful heap when you want early exit on many inputs or when you need to extend the state with more constraints.
Solutions
Solution 1: Limited Bellman-Ford with cloned rounds
Use this as the cleanest interview solution. It directly maps k stops to k + 1 edge-relaxation rounds and avoids the subtle pruning bugs of naive Dijkstra.
Each round allows paths to use one more flight. By relaxing from the previous round's dist into a cloned next array, every update in that round uses at most one additional edge, preserving the stop limit exactly.
Step-by-step
- Set all costs to infinity except dist[src] = 0.
- Repeat k + 1 times, once for each allowed edge count.
- Clone dist into next before scanning flights.
- For each flight from u to v, if u was reachable before this round, improve next[v].
- Assign dist = next and continue.
- Return dist[dst], or -1 if it is still infinity.
O((k + 1) · E)
O(n)
E is flights.length. Each round scans the edge list once and keeps two distance arrays.
Java implementation
Solution 2: Priority queue over city and edge count
Use this when you want a Dijkstra-style early exit, or when the problem adds more state such as coupons, fuel, or remaining transfers. The important difference from naive Dijkstra is that the state includes edges used.
Run a best-first search by cost, but keep separate best costs for each city and number of edges used. A city reached with two different edge counts can lead to different feasible futures, so both states may be worth keeping.
Step-by-step
- Build a directed adjacency list of flights.
- best[city][edges] stores the cheapest cost to reach city using exactly edges flights.
- Push (0 cost, src, 0 edges) into the heap.
- Pop the cheapest state. If it is dst, return its cost because the heap is ordered by cost among feasible states.
- If the state already used k + 1 edges, do not expand it.
- Otherwise relax outgoing flights into states with edges + 1.
O((k + 1) · E · log(n · (k + 2)))
O(n · (k + 2) + E)
The expanded graph has one layer per allowed edge count.
Java implementation
Dry Run
Sample input
Limited Bellman-Ford trace for n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1. Because k = 1, at most 2 edges are allowed.
| Round | Allowed edges | dist before | Updates from previous round | dist after |
|---|---|---|---|---|
| 0 | 0 | [0, ∞, ∞] | source only | [0, ∞, ∞] |
| 1 | 1 | [0, ∞, ∞] | 0 → 1 gives 100; 0 → 2 gives 500 | [0, 100, 500] |
| 2 | 2 | [0, 100, 500] | 1 → 2 gives 200 using previous 100 | [0, 100, 200] |
| answer | up to 2 | [0, 100, 200] | dst cost is finite | return 200 |
The clone prevents the first round from using 0 → 1 and then immediately 1 → 2. That two-flight route becomes legal only in round 2, exactly matching the edge budget.
Interview Tips
This problem is a trap for candidates who recite Dijkstra without checking the state. Explain why one best cost per city is insufficient, then present the limited Bellman-Ford solution because it is short and rigorous. Emphasise clone per round and k + 1 edges. If you choose the heap solution, repeatedly say that city alone is not the node in the search graph; city plus edges used is.
Likely follow-ups
- Return the route itself. Store predecessor information per city and edge count.
- What if there are discount coupons that can be used on up to d flights? Add coupons used to the state dimension.
- What if k is very large? The problem approaches ordinary single-source shortest path with non-negative weights.
- Can prices be negative? Use Bellman-Ford style relaxation and discuss cycle constraints.
Similar Problems
Key Takeaways
- At most k stops means at most k + 1 edges.
- Limited Bellman-Ford is often the cleanest way to enforce an edge budget.
- Clone the distance array each round so one round cannot chain multiple new flights.
- Naive Dijkstra by city alone is wrong when feasibility depends on stops used.