from __future__ import annotations

from collections.abc import Hashable, Iterable, Mapping
from heapq import heappop, heappush
from itertools import count
from math import inf
from typing import TypeAlias, TypeVar


NodeT = TypeVar("NodeT", bound=Hashable)
Graph: TypeAlias = Mapping[NodeT, Iterable[tuple[NodeT, float]]]


def dijkstra_shortest_path(
    graph: Graph[NodeT],
    start: NodeT,
    goal: NodeT,
) -> tuple[float, list[NodeT]]:
    """Return the shortest distance and path from start to goal."""
    distances: dict[NodeT, float] = {start: 0.0}
    previous: dict[NodeT, NodeT] = {}

    # The counter prevents heap comparisons between arbitrary node objects.
    tie_breaker = count()
    heap: list[tuple[float, int, NodeT]] = [(0.0, next(tie_breaker), start)]
    visited: set[NodeT] = set()

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

        if current in visited:
            continue

        visited.add(current)

        if current == goal:
            return current_distance, _reconstruct_path(previous, start, goal)

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

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

    return inf, []


def _reconstruct_path(
    previous: Mapping[NodeT, NodeT],
    start: NodeT,
    goal: NodeT,
) -> list[NodeT]:
    path = [goal]
    current = goal

    while current != start:
        current = previous[current]
        path.append(current)

    path.reverse()
    return 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": [],
    }

    distance, path = dijkstra_shortest_path(graph, "A", "D")
    assert distance == 4
    assert path == ["A", "C", "B", "D"]

    distance, path = dijkstra_shortest_path(graph, "D", "A")
    assert distance == inf
    assert path == []

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


if __name__ == "__main__":
    _run_tests()