Proficient Level
Implement the cheapestFlightWithinKStops method that finds the cheapest price from source to destination within a stop limit.
You are given flight routes as [from, to, price], the number of cities, a source city, a destination city, and the maximum number of allowed stops.
Return the cheapest price from source to destination using at most that many intermediate stops. If the destination cannot be reached within the limit, return -1.
Use a bounded Bellman-Ford style dynamic programming approach.
With at most k stops, the path may use at most k + 1 flights. Repeatedly relax all flights, but each round must use a copy of the previous distances so that one round adds only one more flight.
After k + 1 rounds, the destination distance is the cheapest valid price.
Pseudocode:
function cheapestFlightWithinKStops(nodes, flights, size, source, destination, stops):
distance = array filled with infinity
distance[source] = 0
repeat stops + 1 times:
nextDistance = copy of distance
for each flight [from, to, price]:
if distance[from] is not infinity:
nextDistance[to] = min(nextDistance[to], distance[from] + price)
distance = nextDistance
if distance[destination] is infinity:
return -1
return distance[destination]