Sponsored
Sponsored
In this approach, use BFS to explore all possible paths. Utilize a queue to store the current node, accumulated cost, and the number of stops made so far. The key is to traverse by layer, effectively managing the permitted stops through levels of BFS. If we reach the destination within the allowed stops, track the minimum cost.
Time Complexity: O(n * k) in the worst case when every city is connected.
Space Complexity: O(n) for storing the graph and queue.
1function findCheapestPrice(n, flights, src, dst, k) {
2 const adjList = {};
3 flights.forEach(([start, end, price]) => {
4 if (!adjList[start]) adjList[start] = [];
5 adjList[start].push([end, price]);
6 });
7
8 const queue = [[src, 0, k + 1]];
9 let minCost = Infinity;
10
11 while (queue.length > 0) {
12 const [city, cost, stops] = queue.shift();
13 if (city === dst) {
14 minCost = Math.min(minCost, cost);
15 continue;
16 }
17 if (stops > 0) {
18 (adjList[city] || []).forEach(([nextCity, price]) => {
19 if (cost + price < minCost) {
20 queue.push([nextCity, cost + price, stops - 1]);
21 }
22 });
23 }
24 }
25 return minCost === Infinity ? -1 : minCost;
26}This JavaScript code mirrors the Python implementation: flights are first organized into an adjacency list for the graph representation. The BFS uses a queue initialized with the starting city, zero cost, and k+1 allowable stops. Each current city node is checked against the destination, updating minCost as needed, while neighbors are enqueued only if doing so keeps cumulative costs beneath the current known minimum.
This approach leverages a modified version of Dijkstra's algorithm to explore paths from source to destination using a prioritized data structure like a min-heap. Each entry tracks not only the cumulative cost but also the number of stops taken. The algorithm ensures the shortest paths are evaluated first and skips any path with exceeding stops, thus efficiently finding the minimum cost path within allowed stops.
Time Complexity: O((n+k) log n) reflects edge processing and heap operations.
Space Complexity: O(n) taken by the adjacency list and tracking structures.
1import java.util.*;
2
The Java implementation mirrors the C++ approach, using a priority queue to prioritize lower-cost paths. It explores options similarly: starting from the source, evaluating all connections recursively while updating path costs and stops. By prioritizing by cost, notably using lambda expressions, it ensures the most cost-effective paths are considered first.