Proof of `Each objective attains its optimum`
groundedproofs/Lax330177Proofs/OptimalPaths.lean · lax-330177
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
For each of hop count, elapsed time, arrival time and total waiting, collect the values attained by feasible paths. If a feasible path exists, each collection is a nonempty set of natural numbers and has a least member. A path attaining that member is optimal for the chosen criterion. For latest departure, minimize the deadline minus the departure time. Every feasible departure is at or before the deadline, so a path minimizing this difference departs as late as possible.