Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra algorithm solution in Clear category for The Cheapest Flight by Rcp8jzd
from collections import defaultdict
from typing import List
def cheapest_flight(flights: List, departure: str, arrival: str) -> int:
"""
Calculates the shortest path between start and end points using the
Dijkstra algorithm
:param flights: the flights as arrays of 3 elements - 2 city names as a
string, and a flight price
:param departure: The start city
:param arrival: The arrival city
:return: cheapest price between departure and arrival or 0 if no possible
path exists
"""
# Initialization
graph = defaultdict(dict)
for city1, city2, price in flights:
graph[city1][city2] = price
graph[city2][city1] = price
queue = list(graph.keys())
path = {node: float("inf") for node in queue}
path[departure] = 0
# Dijkstra algorithm: main loop
while queue:
# find the city with a minimal cost
current = min(queue, key=lambda city: path[city])
queue.remove(current)
for i in graph[current]:
# compare alternatives and choose the shortest
alternate = graph[current][i] + path[current]
if path[i] > alternate:
path[i] = alternate
return 0 if path[arrival] == float("inf") else path[arrival]
April 4, 2020
