from __future__ import annotations

import heapq
from collections.abc import Hashable, Iterable, Mapping
from math import inf
from typing import TypeVar

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


def dijkstra(graph: Graph[Node], start: Node) -> tuple[dict[Node, float], dict[Node, Node | None]]:
    """Return shortest distances and predecessors from start."""
    distances: dict[Node, float] = {start: 0.0}
    previous: dict[Node, Node | None] = {start: None}
    heap: list[tuple[float, int, Node]] = [(0.0, 0, start)]
    counter = 1

    while heap:
        current_distance, _, current = heapq.heappop(heap)

        # Skip stale heap entries created before a better path was found.
        if current_distance != distances[current]:
            continue

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

            candidate = current_distance + weight
            if candidate < distances.get(neighbor, inf):
                distances[neighbor] = candidate
                previous[neighbor] = current
                heapq.heappush(heap, (candidate, counter, neighbor))
                counter += 1

    return distances, previous


def shortest_path(graph: Graph[Node], start: Node, goal: Node) -> list[Node] | None:
    """Return the shortest path from start to goal, or None if unreachable."""
    distances, previous = dijkstra(graph, start)
    if goal not in distances:
        return None

    path: list[Node] = []
    current: Node | None = goal
    while current is not None:
        path.append(current)
        current = previous[current]

    return list(reversed(path))


def _run_tests() -> None:
    graph: dict[str, list[tuple[str, float]]] = {
        "A": [("B", 4), ("C", 1)],
        "B": [("D", 1)],
        "C": [("B", 2), ("D", 5)],
        "D": [],
        "E": [("A", 3)],
    }

    distances, _ = dijkstra(graph, "A")
    assert distances == {"A": 0.0, "C": 1.0, "B": 3.0, "D": 4.0}
    assert shortest_path(graph, "A", "D") == ["A", "C", "B", "D"]
    assert shortest_path(graph, "A", "E") is None


if __name__ == "__main__":
    _run_tests()

    sample_graph: dict[str, list[tuple[str, float]]] = {
        "A": [("B", 2), ("C", 5)],
        "B": [("C", 1), ("D", 4)],
        "C": [("D", 1)],
        "D": [],
    }

    print(shortest_path(sample_graph, "A", "D"))