Theorem 12.18 — Dijkstra's algorithm yields shortest paths
ProvedAppliedComb.GraphAlg.dijkstra_correctLet be a finite digraph with edge lengths and let be a root. Run Dijkstra's algorithm (Algorithm 12.14) from , with any admissible choices among ties, until it terminates at Step . Then for every vertex ,
and, whenever , the sequence is a shortest path from to .
This is the correctness theorem for the single-source shortest path problem with non-negative lengths (Problem 12.13): the algorithm computes all distances from together with a shortest path to every vertex.
Formalization Note. The algorithm, its tie-breaking and its halting state are the definition AppliedComb.GraphAlg.Dijkstra; the theorem quantifies over every halted state s (DijkstraRun G r (Fintype.card V) s), so it covers every run. Distances and take values in ℕ∞. The book's theorem speaks of "the distance from to " and "a shortest path" without addressing vertices unreachable from ; for those the distance is the minimum over the empty set, read as , and the first conclusion asserts , while the second conclusion is asserted only for vertices at finite distance (an unreachable vertex has no path at all).
import Mathlib import Definitions.Def_AppliedComb_GraphAlg_Dijkstra
namespace AppliedComb.GraphAlg
/-- Keller–Trotter, p. 251, Theorem 12.18. Dijkstra's algorithm yields shortest paths for every
vertex: when Dijkstra's algorithm (Algorithm 12.14) with root `r` terminates, at Step `n = |V|`,
for each `x ∈ V` the value `δ(x)` is the distance from `r` to `x` and `P(x)` is a shortest path
from `r` to `x`. This holds for every run (every admissible tie-breaking). When no directed path
from `r` to `x` exists the distance is `∞` and the first conclusion says `δ(x) = ∞`; the second
conclusion is asserted for the vertices at finite distance, the only ones having a path. -/
theorem dijkstra_correct {V : Type*} [Fintype V] (G : WeightedDigraph V) (r : V)
(s : DijkstraState V) (hs : DijkstraRun G r (Fintype.card V) s) :
∀ x : V, s.δ x = G.dist r x ∧ (G.dist r x ≠ ⊤ → G.IsShortestPath r x (s.P x)) := by sorry
end AppliedComb.GraphAlg
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The statement concerns an arbitrary vertex type that has finitely many elements. There are no other hypotheses on : it may be empty or have one element. The statement also takes the following objects:
- Graph: is an object of type
WeightedDigraphon (written below). The code shown does not give its definition, so nothing here says what the weights are. It does not say whether they must be non-negative, whether loops or parallel edges are allowed, or what number system the weights live in. - Root: is a vertex.
- State: is an object of type
DijkstraStateon . It is used only through two components:- , a value for each vertex ;
- , which gives an object for each vertex .
- Hypothesis: holds, where is the number of elements of . The code shown does not define this predicate. From its arguments alone, it relates the graph , the root , the natural number and the state . Nothing here says which states satisfy it, or whether any do.
The code also uses two notions attached to that it does not define here:
- Distance: is a value in an ordered type that has a top element . The code compares it with .
- Shortest-path predicate: is a predicate on , and an object .
The meaning of the statement depends entirely on these definitions and on DijkstraRun. They are in the imported file Definitions.Def_AppliedComb_GraphAlg_Dijkstra, which is not shown. The comment attached to the theorem describes them as Keller–Trotter's Theorem 12.18 and Algorithm 12.14. That comment is not part of what the code asserts.
The conclusion is that for every vertex , both of the following hold:
- First claim: it is an exact equality, and it holds for every with no restriction. This includes vertices with , where it says .
- Second claim: it is only an implication. When , nothing is said about .
- Scope: the statement applies to every state that satisfies the hypothesis. It does not say that such a state exists or is unique.
Degenerate cases:
- Empty : and there is no vertex, so no root can be chosen. The statement is then vacuous.
- One vertex: and . The claim is that any state related to by
DijkstraRunhas . If that distance is not , must also satisfy . - Vertices at distance : only the equality is asserted; is unconstrained.
- Unsatisfiable hypothesis: if
DijkstraRunholds for no state with as its count (for example, if its definition indexes steps differently), the theorem is vacuously true. - Undefined notions: whether uses default values or infima of empty sets cannot be read from this code. The same applies to how the weights handle signs and whether is the only value marking unreachability.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.