Label correcting methods are the workhorse family of shortest-path algorithms — Dijkstra's method, Bellman–Ford, SLF/LLL variants and A* all fit the template analyzed in §2.3.1 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005), where shortest paths appear as the purely deterministic face of dynamic programming. The correctness proof (Prop. 2.3.1) is short on paper but genuinely nondeterministic — any node may be removed from the candidate list, children processed in any order — so a formal proof certifies a whole family of concrete algorithms at once.
A finite directed graph with arc set , real arc lengths , origin and destination (BertsekasSPGraph). Walks are nonempty node lists whose consecutive pairs are arcs (BertsekasIsWalkFrom), with length the sum of arc lengths (BertsekasWalkLength); the shortest distance is the infimum of walk lengths in the extended reals, if no walk exists (BertsekasShortestDistance). The standing assumption of §2.3: every cycle has nonnegative length (negative arcs allowed).
The algorithm state (BertsekasLCState) carries labels , the scalar UPPER, and the candidate list OPEN. Initially , all other labels , UPPER , OPEN . One iteration (BertsekasLCStep, nondeterministic): remove any from OPEN; for each child of in any order, if set , and put in OPEN if , or update UPPER if . The algorithm terminates when OPEN is empty.
for every execution, under the nonnegative arc length assumption of §2.3 ( for every arc) — BertsekasDP.label_correcting_correctness_of_nonneg_arcs (goal). Milestones: termination — no infinite execution exists, which needs only the weaker nonnegative-cycle assumption (label_correcting_terminates) — and the workhorse invariant that every finite label is the length of an actual walk from , which needs neither (label_correcting_invariant).
The nonnegative-arc hypothesis is essential and not a formalization artifact: the algorithm prunes with the test , and with a negative arc a longer prefix can still reach more cheaply, so the pruned node is never entered into OPEN. An earlier version of this mission's goal carried only the nonnegative-cycle assumption of §2.1 and was disproved by the counterexample , , , , (a graph with no cycles at all), where the algorithm terminates with while the shortest distance is . Exercise 2.7 of the source treats the nonnegative-cycle case, which requires a modified algorithm.
Prop. 2.3.1 certifies simultaneously breadth-first search, Dijkstra (best-first), depth-first and small-label-first variants — every removal discipline is one refinement of the nondeterministic relation. Formally, the development contributes a reusable small-step framework for label-setting/correcting algorithms on which sharper results (Dijkstra's single-pass property, A* admissibility, §2.3.3) can later be built. The result is classical; the formal content is the induction along the nondeterministic step relation.
Termination is the subtle half: labels do not decrease monotonically along the run in an obvious well-founded way; the book's argument counts the finitely many distinct walk lengths below a bound — this needs the nonnegative-cycle assumption and a careful bound relating labels to simple-path lengths. The invariant proof must thread through the fold over children within a single step.
Finite node type with decidable equality; arcs as a Finset of ordered pairs; lengths total on (only arc values matter). The step relation is fully nondeterministic in pivot choice and child order (a permutation quantifier); correctness quantifies over all reachable terminal states — there is no fixed schedule to exploit. Distances live in EReal, so the no-path case is the honest empty infimum, not a sentinel. The trivializing risk of restricting to nonnegative arcs is avoided: only cycles are constrained.
namespace BertsekasDP
theorem label_correcting_correctness_of_nonneg_arcs {V : Type} [Fintype V] [DecidableEq V]
(G : BertsekasSPGraph V)
(hnn : ∀ i j, (i, j) ∈ G.arcs → 0 ≤ G.length i j)
(σ : BertsekasLCState V)
(hreach : Relation.ReflTransGen (BertsekasLCStep G) (BertsekasLCInit G) σ)
(hterm : σ.openList = ∅) :
σ.upper = BertsekasShortestDistance G G.s G.t := by sorry
end BertsekasDPProposition 2.3.1 (correctness of the label correcting method). Consider the shortest path problem of §2.3 on a finite directed graph with origin and destination , under the standing assumption of that section:
Run the label correcting algorithm from its initial state (, all other labels , , ), with the node removed from and the order of child processing chosen arbitrarily at every iteration. Then for every execution that terminates, i.e. every reachable state with ,
In particular is the shortest path length when a path from to exists, and when none does.
The nonnegative arc hypothesis is essential, not a formalization artifact. Step 2 prunes a child whenever , which is sound only if no suffix from to can have negative length. With a negative arc the pruning discards a node that lies on a cheaper route: for arcs , , — a graph with no cycles at all — the run terminates with while . Exercise 2.7 of the source treats the case where only cycle lengths are assumed nonnegative; that case calls for a modified algorithm.
Formalization Note The statement quantifies over every terminal state reachable by the nondeterministic step relation, so it certifies every removal discipline and every child-processing order simultaneously. The conclusion is an equation in EReal, so the no-path case is the genuine empty infimum .
No open leaves. Every sub-goal is proved or awaiting decomposition.