Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra with priority queue solution in Clear category for The Cheapest Flight by Phil15
from collections import defaultdict
from heapq import heappop, heappush
def cheapest_flight(flights, start, end):
graph = defaultdict(dict)
for A, B, price in flights:
graph[A][B] = graph[B][A] = price
pqueue, price_so_far = [(0, start)], {start: 0}
while pqueue:
price, current = heappop(pqueue)
if current == end:
return price
for new, current_to_new_price in graph[current].items(): # neighbors
new_price = price_so_far[current] + current_to_new_price
if new_price < price_so_far.get(new, float('inf')):
price_so_far[new] = new_price
heappush(pqueue, (new_price, new))
return 0
Jan. 23, 2019
Comments:
