Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra's algorithm solution in Clear category for The Cheapest Flight by David_Jones
from collections import defaultdict
from math import inf
def cheapest_flight(costs, a, b):
G = defaultdict(set)
w, d = {}, {}
for u, v, cost in costs:
G[u].add(v)
G[v].add(u)
w[u,v] = w[v,u] = cost
d[u] = d[v] = inf
d[a] = 0
while d:
u = min(d, key=d.get)
if u == b:
return d[u]
if d[u] == inf:
return 0
for v in G[u]:
if v in d:
d[v] = min(d[v], d[u] + w[u,v])
del d[u]
June 3, 2019
Comments: