from __future__ import annotations

import heapq
from math import inf
from typing import TypeAlias

Node: TypeAlias = str
Graph: TypeAlias = dict[Node, list[tuple[Node, float]]]


def dijkstra(
    graph: Graph, start: Node
) -> tuple[dict[Node, float], dict[Node, Node | None]]:
    """Return shortest distances and predecessors from start."""
    if start not in graph:
        raise KeyError(f"Unknown start node: {start!r}")

    distances = {node: inf for node in graph}
    predecessors: dict[Node, Node | None] = {node: None for node in graph}
    distances[start] = 0.0
    queue: list[tuple[float, Node]] = [(0.0, start)]

    while queue:
        distance, node = heapq.heappop(queue)

        # Ignore stale entries superseded by shorter routes.
        if distance > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            if neighbor not in graph:
                raise KeyError(f"Unknown neighbor: {neighbor!r}")
            if weight < 0:
                raise ValueError("Dijkstra's algorithm requires nonnegative weights")

            candidate = distance + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                predecessors[neighbor] = node
                heapq.heappush(queue, (candidate, neighbor))

    return distances, predecessors


def shortest_path(
    predecessors: dict[Node, Node | None], start: Node, target: Node
) -> list[Node]:
    """Reconstruct a reachable path from start to target."""
    path: list[Node] = []
    current: Node | None = target

    while current is not None:
        path.append(current)
        if current == start:
            return path[::-1]
        current = predecessors.get(current)

    return []


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

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

    try:
        dijkstra({"A": [("A", -1)]}, "A")
    except ValueError:
        pass
    else:
        raise AssertionError("Negative edges must be rejected")


if __name__ == "__main__":
    main()