Tracing Dijkstra on a Small Graph

Follow Dijkstra's shortest-path algorithm node by node on a five-vertex weighted graph, watching the tentative distances settle.

Problem

Dijkstra's algorithm finds shortest paths from a source to all nodes in a graph with non-negative edge weights. It repeatedly finalizes the closest unvisited node and relaxes its outgoing edges, which is optimal because non-negative weights guarantee a finalized distance can never improve later.

Graph

Nodes A..E. Edges: A-B=1, A-C=4, B-C=2, B-D=5, C-D=1, D-E=3. Source is A. The greedy frontier picks the smallest tentative distance each round.

import heapq
G={'A':[('B',1),('C',4)],'B':[('C',2),('D',5)],'C':[('D',1)],'D':[('E',3)],'E':[]}
dist={n:float('inf') for n in G}; dist['A']=0
pq=[(0,'A')]
while pq:
    d,u=heapq.heappop(pq)
    if d>dist[u]: continue
    for v,w in G[u]:
        if d+w<dist[v]:
            dist[v]=d+w; heapq.heappush(pq,(dist[v],v))
print(dist)  # A0 B1 C3 D4 E7

Trace

A finalizes at 0. B is next at 1, and relaxing B improves C to 1+2=3, beating the direct A-C=4. C finalizes at 3 and improves D to 3+1=4. D finalizes at 4 and sets E to 7. The best A-to-E path is A-B-C-D-E, total 7, which no other route matches.

• The priority queue always yields the globally nearest unfinalized node, the crux of correctness.
• Negative edges break the algorithm; use Bellman-Ford instead when weights can be negative.
• Path-planning variants of this logic route cooling and cabling in Kronos plant-layout studies.