"""

Dijkstra's Shortest-Path Algorithm (Heap-Optimised)

Computes single-source shortest paths in a graph with non-negative edge

weights using a min-heap (priority queue) for efficient vertex selection.

This adjacency-list implementation is faster than the O(V²) matrix version

for sparse graphs.

Reference: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Complexity:

Time: O((V + E) log V) using a binary heap

Space: O(V + E)

"""

from __future__ import annotations

import heapq

def dijkstra(

graph: dict[str, dict[str, int | float]],

source: str,

target: str = "",

) -> tuple[int | float, list[str]]:

"""Return the shortest distance and path from *source* to *target*.

Args:

graph: Adjacency-list mapping each vertex to a dict of

{neighbour: weight}.

source: Starting vertex.

target: Destination vertex. When empty, compute shortest

distances to all reachable vertices and return the path

to the last vertex relaxed (mainly useful when a target

is provided).

Returns:

A ``(distance, path)`` tuple where *distance* is the total

shortest-path cost and *path* is the list of vertices from

*source* to *target* inclusive. If *target* is unreachable the

distance is ``float('inf')`` and the path is empty.

Examples:

>>> g = {

... "s": {"a": 2, "b": 1},

... "a": {"s": 3, "b": 4, "c": 8},

... "b": {"s": 4, "a": 2, "d": 2},

... "c": {"a": 2, "d": 7, "t": 4},

... "d": {"b": 1, "c": 11, "t": 5},

... "t": {"c": 3, "d": 5},

... }

>>> dijkstra(g, "s", "t")

(8, ['s', 'b', 'd', 't'])

"""

dist: dict[str, int | float] = {v: float("inf") for v in graph}

dist[source] = 0

prev: dict[str, str | None] = {v: None for v in graph}

heap: list[tuple[int | float, str]] = [(0, source)]

while heap:

d, u = heapq.heappop(heap)

if d > dist[u]:

continue

if u == target:

break

for v, weight in graph[u].items():

alt = dist[u] + weight

if alt < dist.get(v, float("inf")):

dist[v] = alt

prev[v] = u

heapq.heappush(heap, (alt, v))

# Reconstruct path

path: list[str] = []

node: str | None = target if target else None

if node and dist.get(node, float("inf")) < float("inf"):

while node is not None:

path.append(node)

node = prev.get(node)

path.reverse()

return (dist.get(target, float("inf")), path) if target else (0, [])