from __future__ import annotations

import heapq
from collections.abc import Mapping, Sequence
from typing import TypeVar

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


def dijkstra(graph: Graph[Node], start: Node) -> dict[Node, float]:
    """Return shortest distances from start to every reachable node."""
    distances: dict[Node, float] = {start: 0.0}
    heap: list[tuple[float, Node]] = [(0.0, start)]

    while heap:
        current_distance, node = heapq.heappop(heap)

        # Skip stale heap entries left behind after a better 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")

            candidate = current_distance + weight
            if candidate < distances.get(neighbor, float("inf")):
                distances[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))

    return distances


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

    while heap:
        current_distance, node = heapq.heappop(heap)

        if current_distance != distances[node]:
            continue

        if node == goal:
            break

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

            candidate = current_distance + weight
            if candidate < distances.get(neighbor, float("inf")):
                distances[neighbor] = candidate
                previous[neighbor] = node
                heapq.heappush(heap, (candidate, neighbor))

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

    # Reconstruct the path by walking backward from goal to start.
    path: list[Node] = [goal]
    while path[-1] != start:
        path.append(previous[path[-1]])
    path.reverse()

    return distances[goal], 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": [],
    }

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


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