from __future__ import annotations

import heapq
from collections.abc import Hashable
from itertools import count
from typing import TypeAlias, TypeVar

Node = TypeVar("Node", bound=Hashable)
Graph: TypeAlias = dict[Node, list[tuple[Node, float]]]


def dijkstra(graph: Graph[Node], start: Node) -> tuple[dict[Node, float], dict[Node, Node | None]]:
    """Return shortest distances and previous-node links from start."""
    distances: dict[Node, float] = {start: 0.0}
    previous: dict[Node, Node | None] = {start: None}

    tie_breaker = count()
    heap: list[tuple[float, int, Node]] = [(0.0, next(tie_breaker), start)]

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

        # Skip stale heap entries left behind after finding a better route.
        if current_distance != distances[current]:
            continue

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

            new_distance = current_distance + weight
            if new_distance < distances.get(neighbor, float("inf")):
                distances[neighbor] = new_distance
                previous[neighbor] = current
                heapq.heappush(heap, (new_distance, next(tie_breaker), neighbor))

    return distances, previous


def shortest_path(graph: Graph[Node], start: Node, goal: Node) -> tuple[float, list[Node]]:
    """Return the distance and concrete shortest path from start to goal."""
    distances, previous = dijkstra(graph, start)

    if goal not in distances:
        return float("inf"), []

    path: list[Node] = []
    current: Node | None = goal

    while current is not None:
        path.append(current)
        current = previous[current]

    path.reverse()
    return distances[goal], path


def _run_tests() -> None:
    graph: Graph[str] = {
        "A": [("B", 4), ("C", 2)],
        "B": [("C", 1), ("D", 5)],
        "C": [("B", 1), ("D", 8), ("E", 10)],
        "D": [("E", 2)],
        "E": [],
    }

    assert shortest_path(graph, "A", "D") == (7.0, ["A", "C", "B", "D"])
    assert shortest_path(graph, "A", "E") == (9.0, ["A", "C", "B", "D", "E"])
    assert shortest_path(graph, "E", "A") == (float("inf"), [])

    try:
        dijkstra({"A": [("B", -1)]}, "A")
    except ValueError:
        pass
    else:
        raise AssertionError("negative edge weights should raise ValueError")


if __name__ == "__main__":
    _run_tests()

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

    distance, path = shortest_path(sample_graph, "A", "D")
    print(f"distance={distance}, path={path}")