Search
⌘K
Get Premium
Graphs
Cheapest Flights Within K Stops
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
A travel booking system needs to find the lowest-cost route between airports. You're given n cities connected by flights, where each flight [from, to, price] represents a direct route with its cost.
Find the cheapest route from src to dst that uses at most k layovers (intermediate cities). If no such route exists, return -1.
Note: A route with k layovers means visiting k intermediate cities, or equivalently, taking k+1 flights.
Example 1:
Input:
n = 4 flights = [[0,1,100], [1,2,100], [2,3,100], [0,3,500]] src = 0 dst = 3 k = 1
Output:
500
Explanation: The route 0→1→2→3 costs $300 with 2 layovers (cities 1 and 2), which exceeds k=1. The direct flight 0→3 costs $500 with 0 layovers. Even though it's more expensive, it's the only valid route.
Example 2:
Input:
n = 4 flights = [[0,1,100], [1,2,100], [2,3,100]] src = 0 dst = 3 k = 1
Output:
-1
Explanation: The only path 0→1→2→3 requires 2 layovers (cities 1 and 2), but we're limited to k=1. No valid route exists.
Explanation
Understanding the Problem
A flight booking system needs to find the cheapest route between cities, but travelers have a constraint: they don't want too many layovers. Given a network of flights with prices and a maximum number of stops allowed, find the minimum cost to reach the destination.
The key constraint is the stop limit. A "stop" is an intermediate city, so flying A→B→D has 1 stop (city B). If k=1, both routes above are valid. If k=0, only direct flights work.
First Intuition: Can We Use Dijkstra?
This is a shortest path problem. We need to find the cheapest route from source to destination. In Network Delay Time, we used Dijkstra's algorithm to find shortest paths. The algorithm worked beautifully:
- Start from the source with distance 0
- Always pick the cheapest unvisited node
- Update distances to its neighbors
- Once a node is processed, we have its optimal distance
Let's try applying the same approach here. We'll track the minimum cost to reach each city and greedily process the cheapest path first.
Testing Standard Dijkstra
Consider this example: Find the cheapest route from city 0 to city 3 with at most k=1 stops.
Why Standard Dijkstra Fails
The issue: Standard Dijkstra only tracks one value per city, i.e. the minimum cost to reach it. Once we mark a city as "visited" with its cheapest cost, we never reconsider it.
In the example above, standard Dijkstra would process cities in order of increasing cost:
- Start at city 0 with cost $0
- Process city 1 (cost $10), then city 2 (cost $20 via 0→1→2)
- Mark city 2 as "visited" with cost $20
- Reach city 3 with cost $30 via the 0→1→2→3 path
But there's also a more expensive way to reach city 2 which is directly from city 0 for $50. Standard Dijkstra would ignore this path because city 2 is already visited with a cheaper cost of $20.
The problem? The $50 path to city 2 only uses 1 stop, making the route 0→2→3 valid for k=1 (total cost $60). The cheaper $20 path uses 2 stops, making 0→1→2→3 invalid for k=1.
Standard Dijkstra greedily picks the cheapest path and misses the valid but more expensive alternative.
The Solution: Track Both City and Stops
We need to track not just "minimum cost to city X" but "minimum cost to city X using exactly S stops". This means our state must include both:
- State: (cost, city, stops_used)
- Heap: min-heap ordered by cost (same as Dijkstra)
- Visited tracking: best[(city, stops)] = minimum cost to reach city having used exactly stops flights
This creates a state space where the same city can be visited multiple times with different stop counts. Each (city, stops) pair is treated as a distinct state.
How the Algorithm Works
With this modified state, the algorithm becomes:
- Initialize: Add (0, src, 0) to a min-heap (zero cost at source, zero stops used)
- Process states: Pop the cheapest state (cost, city, stops) from the heap
- Check destination: If city == dst, it means we found the cheapest valid route so return cost
- Check constraint: If stops > k, this path exceeds the limit so skip it
- Explore neighbors: For each neighbor, add (cost + price, neighbor, stops + 1) to the heap
- Avoid redundancy: Track best[(city, stops)] to skip states we've seen with lower cost
Because the heap is ordered by cost, the first time we pop the destination city, we're guaranteed it's the cheapest path that satisfies the stop constraint.
This pattern of extending Dijkstra's state with additional constraints appears in many problems: shortest path with fuel limits, paths that must visit certain checkpoints, or paths with time windows. The key is identifying which extra dimension needs tracking.
Walkthrough
Let's trace through flights = [[0,1,100], [1,2,100], [2,3,100], [0,3,500]] with src=0, dst=3, k=1:
Step 1: Initialize
We start at city 0 with no cost and no stops used yet. Our min-heap contains just one state: (0, city=0, stops=0).
Step 2: Process city 0
We pop (0, 0, 0) from the heap. City 0 isn't the destination, so we explore its outgoing flights:
- Flight to city 1 costs $100: add (100, 1, 1) to heap
- Flight to city 3 costs $500: add (500, 3, 1) to heap
Step 3: Process city 1
The min-heap pops (100, 1, 1) since it has the lowest cost. From city 1, we can fly to city 2 for $100, giving total cost $200. We add (200, 2, 2) to the heap.
Now the heap contains (200, 2, 2) and (500, 3, 1). Notice that the state (200, 2, 2) has lower cost but uses 2 flights (stops=2).
Step 4: Process city 2
The heap pops (200, 2, 2). From city 2, we can fly to city 3 for $100, giving total cost $300. We add (300, 3, 3) to the heap.
But, stops=3 means we've taken 3 flights, which corresponds to 2 intermediate cities (1 and 2). This exceeds k=1!
Step 5: Check destination with invalid path
The heap pops (300, 3, 3). City 3 is our destination! But stops=3 > k+1=2, so this path is invalid. We skip it and continue.
Step 6: Found valid path
The heap pops (500, 3, 1). City 3 is the destination, and stops=1 means we took 1 flight (0→3), which has 0 intermediate cities. This is within k=1. Return $500.
Stop counting can be confusing! In this problem, k represents the maximum number of intermediate cities (layovers), not the number of flights. A path with k stops traverses k+1 edges. Our algorithm tracks stops_used which increments with each flight taken. To check validity, we compare stops_used against k+1.
When to Use This Pattern
This modified Dijkstra with state extension is useful when:
| Scenario | State Extension |
|---|---|
| Limited stops/hops | (cost, node, stops) |
| Fuel constraints | (cost, node, fuel_left) |
| Must-visit checkpoints | (cost, node, visited_mask) |
| Time windows | (cost, node, arrival_time) |
Solution
The solution is a straightforward modification of Dijkstra:
- State: (cost, city, stops_used) in a min-heap ordered by cost
- Skip invalid states: If stops > maxStops, continue to next state
- Deduplication: Track best[(city, stops)] to avoid reprocessing
- Return when destination found: First arrival at dst is cheapest valid route
Visualization
Python
Cheapest Flights Within K Stops - Modified Dijkstra
0 / 15
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n · k · log(n · k)) Each (city, stops) pair can be added to the heap once. With n cities and up to k stops, we have O(n·k) states. Each heap operation is O(log(n·k)).
Space Complexity: O(n · k) The heap and best map can each hold O(n·k) entries, one for each (city, stops) combination.
Alternative: Bellman-Ford Approach
An alternative is to use a Bellman-Ford variant: run k+1 iterations, where each iteration relaxes all edges. This gives O(k · E) time complexity. For small k with many edges, this can be more efficient. However, the Dijkstra approach is more intuitive and generalizes better to other constraint types.
Connection to Network Delay Time
Both problems use shortest path algorithms, but:
| Network Delay Time | Cheapest Flights |
|---|---|
| Standard Dijkstra | Modified Dijkstra |
| State: (dist, node) | State: (cost, city, stops) |
| Find min dist to ALL nodes | Find min cost to ONE node |
| Return max of all distances | Return first arrival at dst |
| No hop constraint | Limited to k stops |