The Topology

Tentative Distances

Dijkstra keeps the best distance known so far for each router. Those tentative values are not final until the router is chosen.

highlighted = computed this step

Source starts at zero

Dijkstra starts by giving source A distance 0. Other routers wait for a discovered path.

d(A)=0d(A)=0
Tentative distancesThe router topology is validated as exact nonnegative integer-weighted edges.Tentative distances - weighted undirected topology4251035157ABCDEF

A proposes first distances

A proposes C at 2 and B at 4.

d(C)=2,d(B)=4d(C)=2,\quad{}d(B)=4
Tentative distancesThe router topology is validated as exact nonnegative integer-weighted edges.Tentative distances - weighted undirected topology4251035157ABCDEF

Discovered is not final

A proposed B at 4, but that number is still tentative. Another path could replace it before B is chosen.

d(B)tentative=4d(B)_{\text{tentative}}=4
Tentative distancesThe router topology is validated as exact nonnegative integer-weighted edges.Tentative distances - weighted undirected topology4251035157ABCDEF

Tentative means best so far

C is currently closer because 2 is less than 4.

2<42<4
Tentative distancesThe router topology is validated as exact nonnegative integer-weighted edges.Tentative distances - weighted undirected topology4251035157ABCDEF

Remember who proposed it

Those first claims also remember A as the predecessor for C and B. The predecessor can change only when a smaller claim appears.

predecessor records the best claim\text{predecessor records the best claim}
Tentative distancesThe router topology is validated as exact nonnegative integer-weighted edges.Tentative distances - weighted undirected topology4251035157ABCDEF

Summary

Tentative distances are best-so-far claims that can still improve until their router is chosen as the smallest unsettled router.

tentative best so far\text{tentative best so far}
Tentative distancesThe router topology is validated as exact nonnegative integer-weighted edges.Tentative distances - weighted undirected topology4251035157ABCDEF