# Title: Dijkstra's shortest path
# Heading: Python Program for Dijkstra's Shortest Path Algorithm
# Level: advanced
# Tags: dijkstra, shortest path, weighted graph, heapq, priority queue
# Time: O((V + E) log V)
# Space: O(V + E)
# About: Finds the shortest distance from one node to every other in a weighted graph, always going on from the closest node, with heapq.

import heapq


def dijkstra(graph, start):
    """Shortest distances from start to every reachable node."""
    distances = {start: 0}
    heap = [(0, start)]  # (distance so far, node), closest first
    while heap:
        distance, node = heapq.heappop(heap)
        if distance > distances[node]:
            continue  # out of date: a shorter way was found
        for neighbour, weight in graph[node]:
            new_distance = distance + weight
            if new_distance < distances.get(neighbour, float("inf")):
                distances[neighbour] = new_distance
                heapq.heappush(heap, (new_distance, neighbour))
    return distances


# Each node, and (node, length) for each one-way road leaving it
graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": [("E", 3)],
    "E": [],
}
print("Distances from A:", dijkstra(graph, "A"))