from __future__ import annotations

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

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


def dijkstra(
    graph: Graph[Node], source: Node
) -> tuple[dict[Node, float], dict[Node, Node | None]]:
    """Return shortest distances and predecessors from source."""
    nodes = set(graph)
    for edges in graph.values():
        for neighbor, weight in edges:
            if weight < 0:
                raise ValueError("Dijkstra's algorithm requires nonnegative weights")
            nodes.add(neighbor)

    nodes.add(source)
    distances = {node: math.inf for node in nodes}
    predecessors: dict[Node, Node | None] = {node: None for node in nodes}
    distances[source] = 0.0

    # The counter prevents comparisons between potentially unorderable nodes.
    tie_breaker = count()
    queue: list[tuple[float, int, Node]] = [(0.0, next(tie_breaker), source)]

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

        for neighbor, weight in graph.get(node, ()):
            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                predecessors[neighbor] = node
                heapq.heappush(
                    queue, (candidate, next(tie_breaker), neighbor)
                )

    return distances, predecessors


def reconstruct_path(
    predecessors: Mapping[Node, Node | None], source: Node, target: Node
) -> list[Node]:
    """Reconstruct a reachable path from source to target."""
    if target not in predecessors:
        return []

    path: list[Node] = []
    current: Node | None = target
    while current is not None:
        path.append(current)
        if current == source:
            return list(reversed(path))
        current = predecessors[current]

    return []


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

    distances, predecessors = dijkstra(graph, "A")
    assert distances["D"] == 4
    assert reconstruct_path(predecessors, "A", "D") == ["A", "C", "B", "D"]
    assert math.isinf(distances["E"])
    assert reconstruct_path(predecessors, "A", "E") == []


if __name__ == "__main__":
    main()