Shortest-Path Tree - Routing is a Shortest Path

Once distances are final, each non-source router keeps the predecessor that gave its shortest path. Those predecessors form a tree rooted at A.

highlighted = computed this step

The tree starts at A

The shortest-path tree is rooted at A with distance 0.

d(A)=0

Every router except A contributes one predecessor edge, so this tree has 5 edges.

|T|=5

C sits under A with distance 2, so C's predecessor is A.

\text{pred}(C)=\text{A}

E sits under D with distance 6, matching the relaxation improvement from D.

\text{pred}(E)=\text{D}

The recomputed final distances include D at 5, E at 6, and F at 10.

5,6,10

The displayed tree is not trusted as input; each predecessor and distance is derived from the pinned topology and source.

\text{derived shortest-path tree}