Cheapest Flights Within K Stops
Problem
Given n cities numbered from 0 to n-1, a list of flights where each flight is represented as (source, destination, price), a starting city src, a destination city dst, and an integer k, return the cheapest price from src to dst with at most k stops. If no such route exists, return -1.
- 1 ≤ n ≤ 100
- 0 ≤ flights.length ≤ n * (n - 1) / 2
- flights[i].length == 3
- 0 ≤ src, dst < n
- 0 ≤ k < n
- 1 ≤ price ≤ 10⁴
Example
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1200The algorithm initializes the prices array with infinity except for the source city which is set to 0. It then iteratively relaxes the prices for up to k+1 edges (stops + 1). On the first iteration, it updates the price to city 1 as 100. On the second iteration, it updates the price to city 2 via city 1 as 200, which is cheaper than the direct flight costing 500. Since the maximum allowed stops is 1, this route is valid and the algorithm returns 200.
Approach
Straightforward Solution
A brute-force approach would enumerate all paths from src to dst with up to k stops, calculating their costs and returning the minimum. This approach is exponential in time and infeasible for large inputs.
Core Observation
The problem asks for the minimum cost path from src to dst with at most k stops, which translates to finding the shortest path with a constraint on the number of edges used. This is a classic shortest path problem with an additional constraint on path length.
Path to Optimal
Recognizing the problem as a shortest path with edge constraints suggests using a Dynamic Programming approach similar to the Bellman-Ford algorithm. Bellman-Ford relaxes edges repeatedly to find shortest paths with up to a certain number of edges. Here, iterating k+1 times corresponds to paths with up to k stops (k+1 edges). By copying the prices array at each iteration, the algorithm ensures that updates in the current iteration do not affect other relaxations within the same iteration, preserving correctness.
Optimal Approach
Initialize a prices array with infinity for all cities except the source city set to 0. For k+1 iterations, create a temporary copy of prices. For each flight, if the source city's price is not infinity, update the destination city's price in the temporary array if a cheaper cost is found via this flight. After processing all flights, update the prices array with the temporary array. After k+1 iterations, if the destination city's price is still infinity, return -1; otherwise, return the price. This approach guarantees the cheapest price with at most k stops in O(k * E) time, where E is the number of flights.
Time
O(k * E)
The algorithm performs k+1 iterations, and in each iteration, it processes all E flights to relax edges. Each relaxation is O(1), so total time is O(k * E).
Space
O(n)
The algorithm uses two arrays of size n to store prices and temporary prices. This auxiliary space scales linearly with the number of cities and is necessary to track the minimum costs.
Pattern Spotlight
Dynamic Programming (Bellman-Ford Relaxation with Edge Constraints)
When finding shortest paths with a constraint on the number of edges or stops, iteratively relax edges up to the allowed number of edges, using a temporary array to prevent intra-iteration interference and ensure correctness.
Solution
| 1 | class Solution:
|
| 2 | def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
|
| 3 | prices = [float("inf")] * n
|
| 4 | prices[src] = 0
|
| 5 |
|
| 6 | for i in range(k + 1):
|
| 7 | tmp_prices = prices.copy()
|
| 8 |
|
| 9 | for s, d, p in flights:
|
| 10 | if prices[s] == float("inf"):
|
| 11 | continue
|
| 12 | if prices[s] + p < tmp_prices[d]:
|
| 13 | tmp_prices[d] = prices[s] + p
|
| 14 | prices = tmp_prices
|
| 15 |
|
| 16 | return prices[dst] if prices[dst] != float("inf") else -1 |
Step-by-Step Solution
Initialize Prices Array with Infinite Costs Except Source
| 3 | prices = [float("inf")] * n
|
| 4 | prices[src] = 0
|
Objective
To set up the initial cost estimates for reaching each city, starting with zero cost for the source and infinity for others.
Key Insight
Initializing the prices array with infinity represents that all cities are initially unreachable except the source city, which has zero cost. This setup forms the base case for the iterative relaxation process, allowing the algorithm to progressively find cheaper paths.
Interview Quick-Check
Core Logic
Setting prices[src] = 0 establishes the starting point for cost calculations, ensuring the source city is reachable at zero cost.
Common Pitfalls & Bugs
Failing to initialize non-source cities with infinity would cause incorrect cost comparisons and potentially invalid results.
Iteratively Relax Edges Up to k+1 Times to Update Minimum Prices
| 6 | for i in range(k + 1):
|
| 7 | tmp_prices = prices.copy()
|
| 9 | for s, d, p in flights:
|
| 10 | if prices[s] == float("inf"):
|
| 11 | continue
|
| 12 | if prices[s] + p < tmp_prices[d]:
|
| 13 | tmp_prices[d] = prices[s] + p
|
| 14 | prices = tmp_prices
|
Objective
To progressively update the minimum cost to reach each city by considering all flights up to the allowed number of stops.
Key Insight
Each iteration corresponds to allowing one more edge in the path (one more flight). By copying the prices array at the start of each iteration, the algorithm ensures that all relaxations in the current iteration are based on the previous iteration's costs, preventing premature updates from influencing other relaxations. This mirrors the Bellman-Ford algorithm's approach to shortest path with edge constraints.
Interview Quick-Check
Core Logic
Relaxing all edges in each iteration updates the minimum cost to reach each city with paths of increasing length, up to k+1 edges.
State & Boundaries
The outer loop runs k+1 times because a path with k stops has k+1 edges.
Common Pitfalls & Bugs
Updating the prices array directly within the iteration would cause incorrect cost propagation, violating the edge constraint.
Complexity
This approach runs in O(k * E) time, which is efficient for the problem constraints.
Return the Cheapest Price or -1 if Unreachable
| 16 | return prices[dst] if prices[dst] != float("inf") else -1 |
Objective
To provide the final answer based on the computed minimum cost to reach the destination city.
Key Insight
After all relaxations, if the destination city's price remains infinity, it means no valid path with at most k stops exists. Otherwise, the stored price is the cheapest cost. This conditional return cleanly handles both reachable and unreachable cases.
Interview Quick-Check
Core Logic
Returning -1 when prices[dst] is infinity correctly signals that no valid route exists within the stop constraint.
State & Boundaries
The final prices array reflects the minimum costs after considering all paths with up to k stops.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
tmp_prices = prices.copy()Create a temporary copy of the current prices array.
Copying prices prevents updates in the current iteration from affecting other relaxations, preserving the correctness of the Bellman-Ford relaxation process under edge constraints.
prices[src] = 0Set the source city's price to zero.
This anchors the starting point of the algorithm, indicating that the cost to reach the source city from itself is zero, enabling subsequent relaxations.
if prices[s] + p < tmp_prices[d]:Check if taking this flight offers a cheaper price to the destination city.
This conditional identifies opportunities to improve the minimum cost to reach the destination city by relaxing the edge.
tmp_prices[d] = prices[s] + pUpdate the temporary prices array with the new cheaper price.
Updating tmp_prices instead of prices ensures that all relaxations in the current iteration are based on the previous iteration's costs, preserving the integrity of the relaxation process.
return prices[dst] if prices[dst] != float("inf") else -1Return the cheapest price to the destination or -1 if unreachable.
This conditional return correctly signals whether a valid path within the stop constraint exists, providing the final answer.
prices = [float("inf")] * nInitialize the prices array with infinity for all cities.
Setting all prices to infinity represents that initially, all cities except the source are unreachable, establishing a baseline for cost comparisons.
if prices[s] == float("inf"):Skip flights originating from unreachable cities.
If the source city of a flight is unreachable (price is infinity), relaxing this edge cannot improve any destination cost, so it is skipped to save computation.
prices = tmp_pricesAssign the updated temporary prices back to the main prices array.
This step finalizes the iteration's relaxations, preparing prices for the next iteration or final result extraction.
for i in range(k + 1):Loop k+1 times to allow paths with up to k stops (k+1 edges).
Each iteration corresponds to considering paths with one additional edge, ensuring all valid paths within the stop limit are evaluated.
continueContinue to next flight if source city is unreachable.
This control flow ensures only valid edges from reachable cities are considered, maintaining algorithm correctness and efficiency.
for s, d, p in flights:Iterate over each flight (source, destination, price).
Processing all flights allows the algorithm to consider every possible edge for relaxation in the current iteration.
Test Your Understanding
Why does the algorithm use a temporary copy of the prices array in each iteration instead of updating the prices array directly?
Using a temporary copy prevents updates made in the current iteration from affecting other relaxations within the same iteration, ensuring that all edge relaxations are based on prices from the previous iteration and preserving the correctness of the Bellman-Ford relaxation process.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Cheapest Flights Within K Stops from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Cheapest Flights Within K Stops drill