Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra solution solution in Clear category for The Cheapest Flight by khudr
import heapq
MAX_DISTANCE = 2 ** 31 - 1
def dijkstra(graph, start):
distances = {vertex: MAX_DISTANCE for vertex in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
cur_distance, cur_vertex = heapq.heappop(queue)
if cur_distance > distances[cur_vertex]:
continue
for neighbor, weight in graph[cur_vertex].items():
distance = cur_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
def cheapest_flight(costs: list, a: str, b: str) -> int:
costs += [[cost[1], cost[0], cost[2]] for cost in costs]
vertices = set(cost[0] for cost in costs).union(set(cost[1] for cost in costs))
graph = {vertex: {cost[1]: cost[2] for cost in costs if cost[0] == vertex} for vertex in vertices}
distances = dijkstra(graph, a)
return distances[b] if distances[b] != MAX_DISTANCE else 0
March 18, 2024
Comments:
