Cheapest Flights Within K Stops
Problem Description
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
Constraints:
- 1 <= n <= 100
- 0 <= flights.length <= (n * (n - 1) / 2)
- flights[i].length == 3
- 0 <= fromi, toi < n
- fromi != toi
- 1 <= pricei <= 104
- There will not be any multiple flights between two cities.
- 0 <= src, dst, k < n
- src != dst
Solve it on LeetCode
Approaches
1. Modified Depth-First Search with Pruning
Intuition:
This approach involves using a modified DFS algorithm to explore all possible routes from the source to the destination, while pruning unnecessary paths based on constraints (i.e., the number of stops).
- Use a recursive DFS method to visit all nodes.
- If the number of stops exceeds
K, return as we cannot make more stops. - Track the currently accumulated cost; if it exceeds the known minimum cost for reaching the destination, prune that path.
- Use the adjacency list to explore every neighboring node recursively.
- Update the result whenever a valid path with a cost lower than the current known minimum is found.
Code:
- Time Complexity: O(K * E)) where E is the number of flights, as for every node we are exploring up to K+1 times.
- Space Complexity: O(V + E) where V is the number of vertices. Storage for the graph and call stack for recursion.
2. Bellman-Ford Algorithm (Dynamic Programming)
Intuition:
Bellman-Ford is a classic dynamic programming algorithm that can be adapted to this problem with modifications to accommodate the stop constraint.
- Use a 2D DP array
dpwheredp[i][j]represents the minimum cost to reach cityjusing at mostistops. - Initialize
dp[0][src]to 0 because starting at the source requires no cost, and the rest to infinity. - Update costs for flights up to
K+1times to ensure the number of stops doesn't exceedK.
Code:
- Time Complexity: O(K * E) where E is the number of flights, iterating through flights for
K+1times. - Space Complexity: O(K * V) for storing DP table.
3. Dijkstra's Algorithm
Intuition:
A priority queue (min-heap) can help us always extend the least costly current flight path using a variant of Dijkstra's algorithm that's modified to account for the maximum number of allowed stops.
- Use a priority queue to always select the current minimum cost path.
- Keep track of costs and number of stops made.
- If we reach a destination before exceeding
Kstops, we found the solution. - Use an array to store the minimum cost to reach each city within a certain number of stops.
Code:
- Time Complexity: O(E log V)) where E is the number of flights. The log factor comes from the priority queue.
- Space Complexity: O(V * E) due to adjacency list and priority queue.