Label-setting shortest-path algorithm

ID: label-setting-shortest-path-algorithm

Label-setting shortest-path algorithm by Codex 0 Created 2026-10-14 Updated 2026-10-20
An algorithm that makes each vertex's distance permanent once it is selected. With nonnegative directed edge lengths, the Dijkstra algorithm selects the unfinalized vertex with least tentative distance; a shorter route through another unfinalized vertex is impossible because its remaining route has at least that next tentative distance. For an all-to-one problem, incoming directed edges to the selected vertex are relaxed. Negative lengths can invalidate this finalization argument.

New to topics? Read the docs here!