Cheapest Flights Within K Stops
You are given n cities numbered from 0 to n - 1.
You are also given a list of flights:
flights[i] = [from, to, price]
where a flight goes from from to to with the given price.
You are given:
- src — starting city
- dst — destination city
- k — maximum number of stops allowed
Return the cheapest price from src to dst using at most k stops.
If no such route exists, return:
-1
Example
n = 4
flights =
[0,1,100]
[1,2,100]
[2,3,100]
[0,3,500]
src = 0
dst = 3
k = 1
Possible routes:
0 → 3 = 500
and:
0 → 1 → 2 → 3 = 300
But the second route has 2 stops, which is greater than k = 1.
Therefore:
500
Main Idea
This is a Graph + Shortest Path + Dynamic Programming problem.
A normal Dijkstra algorithm is not enough by itself because we also have a restriction on the number of stops.
A simple approach is Bellman-Ford style relaxation.
If we are allowed at most k stops, we can use at most:
k + 1 flights
Steps
- Store the minimum cost to reach every city.
Initially:
cost[src] = 0
- Relax all flights once.
- Repeat this process k + 1 times.
- After each round, update the cost of reaching destinations using one additional flight.
- Return cost[dst].
Use a separate copy of the distance array during each round so that one iteration represents exactly one additional flight.
Example 1
Input
4 4 0 1 100 1 2 100 2 3 100 0 3 500 0 3 1
Output
500
Explanation
With at most 1 stop, we can use at most 2 flights.
Direct route:
0 → 3 = 500
The cheaper route:
0 → 1 → 2 → 3 = 300
has 2 stops, so it is not allowed.
Therefore:
500
Example 2
Input
3 3 0 1 100 1 2 100 0 2 500 0 2 1
Output
200
Explanation
With at most 1 stop:
0 → 1 → 2
is allowed.
Cost:
100 + 100 = 200
which is cheaper than:
0 → 2 = 500
Therefore:
200
Constraints
Hints:
Hint 1
At most k stops means you can take at most:
k + 1 flights
Hint 2
Maintain:
cost[i]
as the cheapest price to reach city i.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 16, 2026
Last updated
Aug 17, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output