Dijkstra’s Algorithm

Why Finding the Goal Once Isn’t Enough

Suppose a delivery van leaves Depot heading for Home. A direct highway from Depot → Home costs 12 km, so Home enters our frontier immediately on step 1! If we stopped the first time we saw Home, we would report 12 km.

Instead, Dijkstra puts (12, "Home") into a min-heap alongside Park (2), Market (4), and Bridge (6) — and always asks: which waiting offer is closest to Depot right now?

1. Pop Park at 2 km → discovers Depot → Park → Bridge for 2 + 1 = 3 km (beating 6 km!).
2. Pop Bridge at 3 km → discovers Bridge → Home for 3 + 5 = 8 km (beating 12 km!).
3. Pop Market at 4 km → discovers Market → Home for 4 + 3 = 7 km (beating 8 km!).
4. Pop outdated (6, "Bridge") → 6 != distances["Bridge"] (3), so skip immediately!
5. Pop Home at 7 km → every remaining entry in the heap is ≥ 7 km, so with nonnegative road weights, no future detour can ever beat 7 km.

Why Lazy Heap Entries Beat decrease-key in Python

Textbooks often describe mutating an existing priority-queue item in place (decrease_key). Standard binary heaps in Python (heapq), C++ (std::priority_queue), and Java (PriorityQueue) do not expose indexed decrease_key because tracking array indices as elements sift up and down adds pointer bookkeeping overhead to every swap.

Instead, we push the improved (candidate, neighbor) tuple straight onto pending and guard the loop with a two-line staleness check:

cost, node = heappop(pending)
if cost != distances[node]:
    continue

At most E offers can ever be pushed, so the heap holds at most O(E) items. Since log(E) ≤ log(V²) = 2 log(V), heappop and heappush still run in O(log V) time!

Clean Python Implementation

from heapq import heappop, heappush
from math import inf


def rebuild_path(previous: dict[str, str], goal: str) -> list[str]:
    path = [goal]
    while path[-1] in previous:
        path.append(previous[path[-1]])
    path.reverse()
    return path


def shortest_path(
    graph: dict[str, list[tuple[str, int]]],
    start: str,
    goal: str,
) -> tuple[float, list[str]]:
    distances = {node: inf for node in graph}
    distances[start] = 0
    previous: dict[str, str] = {}
    pending = [(0, start)]

    while pending:
        cost, node = heappop(pending)
        if cost != distances[node]:
            continue
        if node == goal:
            return cost, rebuild_path(previous, goal)

        for neighbor, weight in graph[node]:
            if weight < 0:
                raise ValueError("Dijkstra requires nonnegative edge weights")
            candidate = cost + weight
            if candidate < distances[neighbor]:
                distances[neighbor] = candidate
                previous[neighbor] = node
                heappush(pending, (candidate, neighbor))

    return inf, []

When Does Dijkstra Fail?

Dijkstra’s correctness proof hinges on candidate = cost + weight >= cost whenever weight >= 0:

• Zero-weight edges & zero-cost cycles (weight == 0): Completely safe! Strict inequality candidate < distances[neighbor] prevents infinite looping around zero-cost cycles.
• Negative edge weights (weight < 0): Unsafe. A node popped early at cost 4 assumes a later frontier node at cost 6 can never reach it for less than 6 — an edge of -5 (6 + (-5) = 1) shatters that invariant. When negative weights exist, use Bellman-Ford (O(V · E)) instead.