Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for The Cheapest Flight by colinmcnicholl
from collections import defaultdict
import math
from operator import itemgetter
def create_graph(a):
G = defaultdict(dict)
for dep_city, dest_city, price in a:
G[dep_city][dest_city] = price
G[dest_city][dep_city] = price
return G
def Dijkstra(G, s):
"""Input: directed graph G = (V,E) in adjacency-list representation, a vertex
s in set V, a length le >= 0 for each e in set E.
Postcondition: for every vertex v, the value len(v) equals the true
shortest-path distance dist(s,v).
"""
# Initialization.
explored = set(s)
unexplored = set(G.keys()) - explored
shortest_paths = {}
shortest_paths[s] = 0
all_edges = set()
for k, v in G.items():
tail = k
heads = v.keys()
edges = set([(tail, head) for head in heads])
all_edges.update(edges)
for v in unexplored:
shortest_paths[v] = math.inf
# Main loop.
while any([True for v,w in all_edges if v in explored and w not in explored]):
candidate_edges = []
for (v,w) in all_edges:
if v in explored and w not in explored:
score = shortest_paths[v] + G[v][w]
candidate_edges.append(((v,w), score))
best_edge = min(candidate_edges, key=itemgetter(1))
v, w = best_edge[0]
explored.add(w)
shortest_paths[w] = shortest_paths[v] + G[v][w]
return shortest_paths
def cheapest_flight(a, b, c):
"""Input: 3 arguments: the flight schedule as an array of arrays, city of
departure and destination city.
Output: Int. The best price.
"""
G = create_graph(a)
prices = Dijkstra(G, b)
cheapest_price = prices[c]
if cheapest_price < math.inf:
return cheapest_price
else:
return 0
if __name__ == '__main__':
print("Example:")
print(cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'A',
'C'))
# These "asserts" are used for self-checking and not for an auto-testing
assert cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'A',
'C') == 70
assert cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'C',
'A') == 70
assert cheapest_flight([['A', 'C', 40],
['A', 'B', 20],
['A', 'D', 20],
['B', 'C', 50],
['D', 'C', 70]],
'D',
'C') == 60
assert cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['D', 'F', 900]],
'A',
'F') == 0
assert cheapest_flight([['A', 'B', 10],
['A', 'C', 15],
['B', 'D', 15],
['C', 'D', 10]],
'A',
'D') == 25
print("Coding complete? Click 'Check' to earn cool rewards!")
Jan. 24, 2019
Comments:
