Cheapest Flights Within K Stops
There are n cities connected by m flights. Each flight starts from city a and arrives at city b with a price c. Find the cheapest price from city 0 to city destination with at most k stops. If there is no route from city 0 to city destination with at most k stops, output -1.
Constraints:
- 1 <= n <= 100
- 0 <= m <= 10000
- 0 <= k <= 100
- 0 <= a, b < n
- 1 <= c <= 10000
- 0 <= destination < n
Examples:
Input: [[[0,1,100],[1,2,100],[0,2,500]],2,0,2]
Output: 200
Explanation: The cheapest price from city 0 to city 2 with at most 2 stops is 200, which is achieved by flying from city 0 to city 1 and then from city 1 to city 2.
Solutions
Bellman-Ford Algorithm
The Bellman-Ford algorithm is used to find the shortest path from the source city to all other cities in the graph. The algorithm is run k + 1 times to ensure that the shortest path with at most k stops is found.
function findCheapestPrice(n, flights, k, src, dst) {
let prices = new Array(n).fill(Infinity);
prices[src] = 0;
for (let i = 0; i <= k; i++) {
let currPrices = [...prices];
for (let [a, b, c] of flights) {
if (prices[a] !== Infinity && prices[a] + c < currPrices[b]) {
currPrices[b] = prices[a] + c;
}
}
prices = currPrices;
}
return prices[dst] === Infinity ? -1 : prices[dst];
}
Follow-up:
What if the graph contains negative weight edges?
