Graphs

Dijkstra Small Graph

Run Dijkstra on positive integer edge weights. This is a small deterministic example, not solver engineering.

Example

Run Dijkstra on positive integer edge weights.

highlighted = computed this step

Step 1 — Dijkstra row

Compute the highlighted combinatorics value.

visit, distances, previous(A, (0, 2, 5, 99, 99), (-, A, A, -, -))\begin{array}{c|c}\text{visit, distances, previous}&\hlmath{\text{(A, (0, 2, 5, 99, 99), (-, A, A, -, -))}}\end{array}

Step 2 — Dijkstra row

Compute the highlighted combinatorics value.

visit, distances, previous(B, (0, 2, 3, 6, 99), (-, A, B, B, -))\begin{array}{c|c}\text{visit, distances, previous}&\hlmath{\text{(B, (0, 2, 3, 6, 99), (-, A, B, B, -))}}\end{array}

Step 3 — Dijkstra row

Compute the highlighted combinatorics value.

visit, distances, previous(C, (0, 2, 3, 4, 10), (-, A, B, C, C))\begin{array}{c|c}\text{visit, distances, previous}&\hlmath{\text{(C, (0, 2, 3, 4, 10), (-, A, B, C, C))}}\end{array}

Step 4 — Dijkstra row

Compute the highlighted combinatorics value.

visit, distances, previous(D, (0, 2, 3, 4, 7), (-, A, B, C, D))\begin{array}{c|c}\text{visit, distances, previous}&\hlmath{\text{(D, (0, 2, 3, 4, 7), (-, A, B, C, D))}}\end{array}

Step 5 — Dijkstra row

Compute the highlighted combinatorics value.

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