π Problem Details
- Title:
787. Cheapest Flights Within K Stops
- Link: https://leetcode.com/problems/cheapest-flights-within-k-stops/
- Difficulty: Medium
- Tags/Categories: Graphs
input integer
n
representing the number of cities connected by some number of flights input arrayflights
βflights[i] = [from, to, price]
input integers:src
dst
k
return the cheapest price fromsrc
todst
with at MOSTk
stops return -1 if not possible
πWhat Were My Initial Thoughts?
- we are looking for the shortest path from src to destination with the added constraint that this shortest path in weight cannot exceed k nodes visited
- an extension of dijkstra's shortest path algorithm seems appropriate
- instead of using dijkstra's we can use bellman ford as it works well when we need to limit the number of edges to relax
π‘ Explanation of Solution
Instead of a priority queue, Bellman-Ford relaxes edges k+1
times.
Algorithm:
- Initialize an array
dist[]
withINF
, exceptdist[src] = 0
. - Iterate k+1 times:
- Create a temporary array
temp[]
(copy ofdist[]
). - Relax all flights:
temp[to] = min(temp[to], dist[from] + price)
- Swap
dist[]
withtemp[]
after each iteration.
- Create a temporary array
- Return
dist[dst]
, or-1
if unreachable.
β Complexity Analysis
Time Complexity: O(k * E)
Space Complexity: O(k * E)
π» Implementation of Solution
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<int> dist (n, INT_MAX);
dist[src] = 0;
for(int i = 0; i <= k; i++) {
vector<int> temp = dist; // create a copy for this iteration
for(const auto& flight : flights) {
int from = flight[0];
int to = flight[1];
int weight = flight[2];
if(dist[from] != INT_MAX) {
temp[to] = min(temp[to], dist[from] + weight);
}
}
dist = temp;
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
};