Choose the Smallest - Routing is a Shortest Path

The next settled router is the unsettled router with the smallest tentative distance. The pinned graph has a unique choice at every step.

highlighted = computed this step

Choose C after A

After A, the smallest tentative distance is C at 2.

\min=2

All remaining link weights are nonnegative integers, so no unsettled route can later sneak below C's distance 2.

d(C)=2

After relaxing from C, B at 4 is still smaller than D at 5.

4<5

D at 5 is chosen before E at 6 and F at 10.

5<6<10

The recomputed settled order begins A, then C, then B.

\text{A}\to\text{C}\to\text{B}

The complete settled order is A, C, B, D, E, F. The source comes first, and F is last because its final distance is 10.

\text{A}\to\text{C}\to\text{B}\to\text{D}\to\text{E}\to\text{F}

Choosing the smallest tentative router makes its distance final before the algorithm moves on.

\text{settled prefix fixed}