Proposition 12.17 — Dijkstra's algorithm makes vertices permanent in nondecreasing order of δ
ProvedAppliedComb.GraphAlg.dijkstra_monotoneRun Dijkstra's algorithm (Algorithm 12.14) with root on a digraph with edge lengths in and vertices. When the algorithm halts, let be the sequence of permanent vertices. Then
The claim holds for every run of the algorithm, i.e. for every way of choosing among temporary vertices of equal minimum . It is the second ingredient of the correctness proof of Theorem 12.18.
Formalization Note. A halted state is a state s with DijkstraRun G r (Fintype.card V) s; the conclusion says that the list s.σ.map s.δ of values in (ℕ∞) is a chain for ≤.
import Mathlib import Definitions.Def_AppliedComb_GraphAlg_Dijkstra
namespace AppliedComb.GraphAlg
/-- Keller–Trotter, p. 251, Proposition 12.17. When Dijkstra's algorithm (Algorithm 12.14) with
root `r` halts, at Step `n = |V|`, let `σ = (v₁, v₂, …, vₙ)`. Then
`δ(v₁) ≤ δ(v₂) ≤ ⋯ ≤ δ(vₙ)`. This holds for every run, i.e. for every admissible way of
breaking ties when a temporary vertex of minimum `δ` is chosen. -/
theorem dijkstra_monotone {V : Type*} [Fintype V] (G : WeightedDigraph V) (r : V)
(s : DijkstraState V) (hs : DijkstraRun G r (Fintype.card V) s) :
(s.σ.map s.δ).IsChain (· ≤ ·) := by sorry
end AppliedComb.GraphAlg
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setup:
- is a finite vertex type with .
- is a weighted digraph on , and is a vertex.
- is a state that is a run state of Dijkstra's algorithm with root at step . Such a state is reached through three rules:
- the initial state at step ;
- choosing a minimal temporary vertex at step , with no scan;
- repeatedly, for , scanning from the last permanent vertex and then appending a temporary vertex of minimum . Every tie-breaking choice gives a run.
Let be the list of permanent vertices of , and the value function of , with values in . The theorem asserts
with each consecutive pair compared in the order of , where is the largest element. The statement says nothing about:
- the length of ;
- whether lists every vertex;
- how relates to true distances.
Degenerate cases.
- If , the only run state at step is the initial state. Then , and the assertion is trivially true for a one-element list.
- cannot occur, since the vertex exists.
- Vertices whose value is (for instance, vertices never reached through edges) may appear, and the inequalities then permit .
- The final state has not been scanned from its last vertex . The values of permanent vertices are the ones they held when they became permanent, unchanged by later scans.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.