Problem Link : 787. Cheapest Flights Within K Stops [LeetCode]
Problem Level : Medium
Topics : Dynamic Programming, Depth-First Search, Breadth-First, SearchGraphHeap (Priority Queue)
Problem Description : 787. Cheapest Flights Within K Stops
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 <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dst
Solution :
Graph Representation:
- The given flights are used to construct an adjacency list graph.
Dijkstra’s Algorithm:
- A priority queue (minHeap) is used to explore paths with minimum cost.
- The algorithm iterates until the minHeap is empty.
- For each iteration, it extracts the minimum distance, current node, and remaining stops from the minHeap.
- If the current node is the destination, the minimum distance is returned.
- If the remaining stops are zero, the iteration skips to the next step.
- For each neighbor of the current node, the algorithm updates the distance and adds the neighbor to the heap.
Time and Space Complexity:
- The time complexity is determined by the priority queue operations, resulting in O(E + V * log(V)) where E is the number of flights and V is the number of cities.
- The space complexity is O(V * (K + 1)) for the distance array and O(V) for the priority queue.
Code :
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] flight : flights) {
final int u = flight[0];
final int v = flight[1];
final int w = flight[2];
graph[u].add(new Pair<>(v, w));
}
return dijkstra(graph, src, dst, k);
}
private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int dst, int k) {
int[][] dist = new int[graph.length][k + 2];
Arrays.stream(dist).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
// (d, u, stops)
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] – b[0]);
dist[src][k + 1] = 0;
minHeap.offer(new int[] {dist[src][k + 1], src, k + 1});
while (!minHeap.isEmpty()) {
final int d = minHeap.peek()[0];
final int u = minHeap.peek()[1];
final int stops = minHeap.poll()[2];
if (u == dst)
return d;
if (stops == 0)
continue;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (d + w < dist[v][stops – 1]) {
dist[v][stops – 1] = d + w;
minHeap.offer(new int[] {dist[v][stops – 1], v, stops – 1});
}
}
}
return -1;
}
}
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,
int k) {
vector<vector<pair<int, int>>> graph(n);
for (const vector<int>& flight : flights) {
const int u = flight[0];
const int v = flight[1];
const int w = flight[2];
graph[u].emplace_back(v, w);
}
return dijkstra(graph, src, dst, k);
}
private:
int dijkstra(const vector<vector<pair<int, int>>>& graph, int src, int dst,
int k) {
vector<vector<int>> dist(graph.size(), vector<int>(k + 2, INT_MAX));
using T = tuple<int, int, int>; // (d, u, stops)
priority_queue<T, vector<T>, greater<>> minHeap;
dist[src][k + 1] = 0;
minHeap.emplace(dist[src][k + 1], src, k + 1);
while (!minHeap.empty()) {
const auto [d, u, stops] = minHeap.top();
minHeap.pop();
if (u == dst)
return d;
if (stops == 0)
continue;
for (const auto& [v, w] : graph[u])
if (d + w < dist[v][stops – 1]) {
dist[v][stops – 1] = d + w;
minHeap.emplace(dist[v][stops – 1], v, stops – 1);
}
}
return -1;
}
};
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = [[] for _ in range(n)]
for u, v, w in flights:
graph[u].append((v, w))
return self._dijkstra(graph, src, dst, k)
def _dijkstra(self, graph: List[List[Tuple[int, int]]], src: int, dst: int, k: int) -> int:
dist = [[math.inf for _ in range(k + 2)] for _ in range(len(graph))]
dist[src][k + 1] = 0
minHeap = [(dist[src][k + 1], src, k + 1)] # (d, u, stops)
while minHeap:
d, u, stops = heapq.heappop(minHeap)
if u == dst:
return d
if stops == 0:
continue
for v, w in graph[u]:
if d + w < dist[v][stops – 1]:
dist[v][stops – 1] = d + w
heapq.heappush(minHeap, (dist[v][stops – 1], v, stops – 1))
return -1
Output :
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
