= Label-setting shortest-path algorithm
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.
Back to article page
