dijkstra

Dijkstra's algorithm on an undirected weighted graph. Source = $A$. Cells $0..5$ of the $dist$ array track the tentative distance to $A, B, C, D, E, F$ respectively. Initialise $dist[A] = 0$; every other node stays at $\infty$. Push $A$ into the priority queue.

Settle $A$. Relax edge $A\to B$ with weight $4$: $dist[B] = \min(\infty, 0+4) = 4$. Update and keep scanning from $A$.

Relax edge $A\to C$ with weight $2$: $dist[C] = \min(\infty, 0+2) = 2$. $A$ has no more outgoing edges. The smallest tentative distance in the queue is now $dist[C] = 2$.

Pop $C$ (key $= 2$). Settle $C$: this is the final distance because all edge weights are non-negative.

Relax edge $C\to B$ with weight $1$: $dist[B] = \min(4, 2+1) = 3$. The detour $A \to C \to B$ is cheaper than the direct $A \to B$ edge.

Relax edge $C\to D$ with weight $8$: $dist[D] = \min(\infty, 2+8) = 10$. Tentative only – a shorter path through $B$ may appear.

Relax edge $C\to E$ with weight $10$: $dist[E] = \min(\infty, 2+10) = 12$. Still tentative.

Pop $B$ (key $= 3$). Settle $B$. The queue now holds $D=10$ and $E=12$.

Relax edge $B\to D$ with weight $5$: $dist[D] = \min(10, 3+5) = 8$. The new predecessor of $D$ is $B$, not $C$.

Pop $D$ (key $= 8$). Settle $D$.

Relax edge $D\to E$ with weight $2$: $dist[E] = \min(12, 8+2) = 10$. Improved via $A\to C\to B\to D\to E$.

Relax edge $D\to F$ with weight $6$: $dist[F] = \min(\infty, 8+6) = 14$. Tentative.

Pop $E$ (key $= 10$). Settle $E$. Only $F$ remains in the queue with key $14$.

Relax edge $E\to F$ with weight $3$: $dist[F] = \min(14, 10+3) = 13$. One last improvement.

Pop $F$ (key $= 13$). Settle $F$. The priority queue is empty – all nodes are settled.

Shortest-path tree rooted at $A$: $A\!\to\!C$, $C\!\to\!B$, $B\!\to\!D$, $D\!\to\!E$, $E\!\to\!F$. Final distances: $dist = [0, 3, 2, 8, 10, 13]$. Non-tree edges are dimmed; each would form a longer alternative.