How do you find the cheapest flight from a source to a destination with at most k stops?
You relax the edges, and you only allow yourself to use a limited number of flights.
def find_cheapest_flight(n, flights, source, destination, k):
cost = [float('inf')] * n
cost[source] = 0
for _ in range(k + 1):
# Make a copy, so that one round cannot use a flight twice.
next_cost = cost[:]
for u, v, price in flights:
if cost[u] == float('inf'):
continue
if cost[u] + price < next_cost[v]:
next_cost[v] = cost[u] + price
cost = next_cost
if cost[destination] == float('inf'):
return -1
return cost[destination]
So how does it work? The cost array holds the cheapest price to each airport using the number of flights allowed so far. The first round allows one flight, the second round allows two, and so on. After k plus one rounds you have allowed k plus one flights, which is k stops.
And the line next_cost = cost[:] is the important one. You make a copy of the costs at the start of each round, and you write the new prices into the copy. If you wrote them into the same list then a flight could be used more than once inside one round, and you would get routes with more flights than you are allowed.
the flights u, v, price
------------ -------------
0 -> 1 100
1 -> 2 100
2 -> 3 100
with k stops of 1, you can use 2 flights, so the cost to 2 is 200
the answer for 3 is 300
And the complexity is O of k times m for the time, where m is the number of flights, and O of n for the space.
So the rule to remember is this. One round per flight, and always write into a copy of the costs.
The last question in this topic shows the breadth first search version.