§3, p. 1780, the labeling process — with lengths ≥ 0, every run of improving-arc replacements from the initial labels is finite
ProvedFordFulkerson58.ArcChain.labeling_terminateslabeling-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-chaintermination
Let be a network whose arc lengths are all non-negative, and let be a set of nodes. Start the labeling process with on and elsewhere, and repeatedly replace by whenever an arc traversable from to satisfies . Then the process cannot go on forever: there is no infinite sequence of labelings
in which each arises from by one such replacement.
This is the page's "Eventually no such arcs can be found": whatever order the arcs are scanned in, the process stops with a terminal labeling.
Formalization Note Lengths may be ; no strict positivity is assumed. The statement covers every run, not one chosen run.
Preamble
import Mathlib import Definitions.Def_FordFulkerson58_ArcChain_Network import Definitions.Def_FordFulkerson58_ArcChain_Labeling
Formal statement
namespace FordFulkerson58.ArcChain
/-- §3, p. 1780, the labeling process: with non-negative arc lengths, every run of the labeling
process from the initial labels is finite — there is no infinite sequence of improving replacements. -/
theorem labeling_terminates {V E ι : Type*} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
[Fintype ι] [DecidableEq ι] (N : Network V E ι)
(S : Finset V) (l : E → ℝ) (hl : ∀ e, 0 ≤ l e) :
¬ ∃ f : ℕ → V → WithTop ℝ, f 0 = initLabel S ∧ ∀ i, RelaxStep N l (f i) (f (i + 1)) := by sorry
end FordFulkerson58.ArcChain
Source
Ford and Fulkerson, A suggested computation for maximal multi-commodity network flows, Management Sci. 50(12S) (2004), p. 1780, §3, the labeling process ("Eventually no such arcs can be found")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.