Dijkstra, 0–1 BFS and A*

Dijkstra finalises the minimum tentative distance on nonnegative edges. Relax when d[v]>d[u]+w. A negative edge can improve a previously finalised vertex, invalidating the proof; merely having positive cycle totals is insufficient.

With a heap, push improved entries and discard stale entries when popped. Do not mark a vertex final on first enqueue. Early stopping is valid when the target's current minimum entry is extracted.

For0/1 weights, deque-based0–1 BFS runs in O(V+E). A* prioritises f=g+h; admissibility prevents overestimation. Consistency supports graph search without reopening closed nodes; inconsistent heuristics require appropriate reopening. Dijkstra is A* with h=0. Real navigation uses additional preprocessing and traffic models.

Why relaxation is reliable

Let s→a=4, s→b=1 and b→a=2. Initial tentative distances are a=4 and b=1. Popping b improves a to three. Later a=3 is finalised; the remaining heap entry a=4 is stale and skipped when it differs from best[node]. Update parents on successful relaxation; distances alone do not reconstruct paths.

Dijkstra’s proof depends on nonnegative edges. Once the minimum tentative vertex is selected, an unseen cheaper route cannot arrive through another unselected vertex: its prefix is already no smaller and remaining weights are nonnegative. A negative edge invalidates this argument. Bellman-Ford or appropriate Johnson reweighting handles other conditions.

A* prioritises f=g+h. Admissibility never overestimates remaining cost; consistency requires h(u)≤w(u,v)+h(v). Consistency matters for graph-search implementations that do not reopen closed vertices. With h=0, A* becomes Dijkstra. Straight-line geographic distance is a lower bound only for compatible cost models, not arbitrary fees or travel times.

Foundation: Trace the stale heap entry. Intermediate: Test zero-weight edges and unreachable vertices. Advanced: Demonstrate reopening with an admissible but inconsistent heuristic, measuring expansion counts separately from correct distances.

import heapq

def dijkstra(g, start):
    if any(w < 0 for edges in g.values() for _,w in edges):
        raise ValueError("negative edge")
    dist = {u: float("inf") for u in g}; dist[start] = 0
    q = [(0,start)]
    while q:
        d,u = heapq.heappop(q)
        if d != dist[u]: continue
        for v,w in g[u]:
            if d+w < dist[v]:
                dist[v] = d+w; heapq.heappush(q,(dist[v],v))
    return dist
assert dijkstra({"A":[("B",10),("C",1)],"B":[],"C":[("B",2)]},"A")["B"] == 3