from __future__ import annotations

from heapq import heappop, heappush
from itertools import count
from typing import Hashable, Iterable, Mapping, TypeVar

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


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

    # Counter avoids comparing nodes when two queue entries have the same distance.
    tie_breaker = count()
    queue: list[tuple[float, int, Node]] = [(0.0, next(tie_breaker), source)]

    while queue:
        current_distance, _, node = heappop(queue)

        # Ignore stale queue entries created before a shorter path was found.
        if current_distance != distances[node]:
            continue

        for neighbor, weight in graph.get(node, ()):
            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] = node
                heappush(queue, (new_distance, next(tie_breaker), neighbor))

    return distances, previous


def shortest_path(graph: Graph[Node], source: Node, target: Node) -> list[Node]:
    """Return one shortest path from source to target, or [] if unreachable."""
    distances, previous = dijkstra(graph, source)
    if target not in distances:
        return []

    path: list[Node] = []
    current: Node | None = target
    while current is not None:
        path.append(current)
        current = previous[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": [],
    }

    distances, previous = dijkstra(graph, "A")
    assert distances == {"A": 0.0, "C": 1.0, "B": 3.0, "D": 4.0}
    assert previous["D"] == "B"
    assert shortest_path(graph, "A", "D") == ["A", "C", "B", "D"]
    assert shortest_path(graph, "A", "Z") == []

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


if __name__ == "__main__":
    _run_tests()
    print("All tests passed.")