§3, p. 1780 — when the labeling process stops, π_i is the length of a shortest chain from S to P_i; the smallest π_i on T is the S-to-T distance
ProvedFordFulkerson58.ArcChain.terminal_label_eq_shortestcorrectnesslabeling-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1shortest-chain
Let be a network with non-negative arc lengths , let and be sets of nodes, and let be a labeling obtained from the initial labels ( on , elsewhere) by finitely many steps of the labeling process, such that no further step is possible. Then
- for every node , is the length of a shortest chain from to ( if there is none);
- the smallest label on is the length of a shortest chain from to :
This is the correctness of the shortest chain algorithm: the final labels are the shortest-chain distances from the source set.
Formalization Note The labeling must be both reachable from the initial labels and terminal; a terminal labeling alone (for instance all labels ) need not consist of distances. Both minima are (⊤) on empty sets.
Preamble
import Mathlib import Definitions.Def_FordFulkerson58_ArcChain_Network import Definitions.Def_FordFulkerson58_ArcChain_Labeling
Formal statement
namespace FordFulkerson58.ArcChain
/-- §3, p. 1780: when the labeling process (with non-negative lengths) stops, every label is the length
of a shortest chain from `S` to its node, and the smallest label on `T` is the length of a shortest
chain from `S` to `T`. -/
theorem terminal_label_eq_shortest {V E ι : Type*} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
[Fintype ι] [DecidableEq ι] (N : Network V E ι)
(S T : Finset V) (l : E → ℝ) (hl : ∀ e, 0 ≤ l e) (lab : V → WithTop ℝ)
(hrun : Relation.ReflTransGen (RelaxStep N l) (initLabel S) lab) (hterm : IsTerminal N l lab) :
(∀ v, lab v = shortestChainLength N l S v) ∧ T.inf lab = shortestChainLengthTo N l S T := 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 ("then the number π_i represents the length of a shortest chain from S to P_i … In particular")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.