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.
public int findCheapestPrice(int n, int[][] flights, int k, int src, int dst) {
int[] prices = new int[n];
Arrays.fill(prices, Integer.MAX_VALUE);
prices[src] = 0;
for (int i = 0;
i <= k;
i++) {
int[] currPrices = prices.clone();
for (int[] flight : flights) {
int a = flight[0], b = flight[1], c = flight[2];
if (prices[a] != Integer.MAX_VALUE && prices[a] + c < currPrices[b]) {
currPrices[b] = prices[a] + c;
}
}
prices = currPrices;
}
return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
}Follow-up:
What if the graph contains negative weight edges?
