Graph Capstone

Shortest Path Table

Read final distances and predecessors from Dijkstra. This is a small deterministic example, not solver engineering.

Example

Read final distances and predecessors from Dijkstra. For each vertex the table records the shortest total distance from the start and the predecessor, the vertex you arrive from along that best route. Dijkstra fills this by always settling the nearest unsettled vertex first, which guarantees that once a vertex is finalized, no later path can reach it more cheaply.

highlighted = computed this step

Step 1 — Final table

Compute the highlighted combinatorics value.

node, distance, previous((A, 0, -), (B, 2, A), (C, 3, B), (D, 4, C), (E, 7, D))\begin{array}{c|c}\text{node, distance, previous}&\hlmath{\text{((A, 0, -), (B, 2, A), (C, 3, B), (D, 4, C), (E, 7, D))}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.