from __future__ import annotations

import heapq
from collections.abc import Hashable, Mapping, Sequence
from itertools import count
from math import inf
from typing import TypeVar

Node = TypeVar("Node", bound=Hashable)
Graph = Mapping[Node, Sequence[tuple[Node, float]]]


def dijkstra(graph: Graph[Node], start: Node) -> dict[Node, float]:
    """Return the shortest distance from start to every known node."""
    distances = {node: inf for node in graph}
    distances[start] = 0.0

    # The counter avoids comparing nodes when distances are equal.
    order = count()
    queue: list[tuple[float, int, Node]] = [(0.0, next(order), start)]

    while queue:
        distance, _, node = heapq.heappop(queue)
        if distance != distances[node]:
            continue  # Ignore stale queue entries.

        for neighbor, weight in graph.get(node, ()):
            if weight < 0:
                raise ValueError("Dijkstra's algorithm requires non-negative weights")

            candidate = distance + weight
            if candidate < distances.get(neighbor, inf):
                distances[neighbor] = candidate
                heapq.heappush(queue, (candidate, next(order), neighbor))

    return distances


def _run_tests() -> None:
    graph = {
        "A": [("B", 4), ("C", 1)],
        "B": [("D", 1)],
        "C": [("B", 2), ("D", 5)],
        "D": [],
        "E": [],
    }
    assert dijkstra(graph, "A") == {
        "A": 0.0,
        "B": 3.0,
        "C": 1.0,
        "D": 4.0,
        "E": inf,
    }

    # Neighbors need not appear as top-level adjacency-list keys.
    assert dijkstra({"A": [("B", 2)]}, "A") == {"A": 0.0, "B": 2.0}


if __name__ == "__main__":
    _run_tests()