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.
def findCheapestPrice(n, flights, k, src, dst):
prices = [float('inf')] * n; prices[src] = 0; for _ in range(k + 1):
curr_prices = prices[:] for a, b, c in flights:
if prices[a] != float('inf') and prices[a] + c < curr_prices[b]:
curr_prices[b] = prices[a] + c prices = curr_prices return -1 if prices[dst] == float('inf') else prices[dst]Follow-up:
What if the graph contains negative weight edges?
