Proposition 12.16 — subpaths of shortest paths are shortest paths
ProvedAppliedComb.GraphAlg.shortest_path_subpathscombinatoricsgraph-theoryp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1shortest-paths
Let be a digraph with edge lengths in , let be a vertex, and let be a shortest path from to . Then for every integer with ,
This optimal-substructure property of shortest paths is the first ingredient of the correctness proof of Dijkstra's algorithm (Theorem 12.18).
Formalization Note. The path is a list P with and = P[j]; the prefix is P.take (j + 1) and the suffix is P.drop j. Directed paths, their lengths and shortest paths are those of the definition AppliedComb.GraphAlg.Dijkstra (paths have distinct vertices).
Preamble
import Mathlib import Definitions.Def_AppliedComb_GraphAlg_Dijkstra
Formal statement
namespace AppliedComb.GraphAlg
/-- Keller–Trotter, p. 251, Proposition 12.16. Let `P = (r = u₀, u₁, …, u_t = x)` be a shortest
path from `r` to `x` in a digraph with edge lengths in `ℕ₀`. Then for every integer `j` with
`0 < j < t`, `(u₀, …, u_j)` is a shortest path from `r` to `u_j` and `(u_j, …, u_t)` is a
shortest path from `u_j` to `u_t`. Here `t = |P| − 1`, `u_j = P[j]`, the prefix is
`P.take (j + 1)` and the suffix is `P.drop j`. -/
theorem shortest_path_subpaths {V : Type*} (G : WeightedDigraph V) (r x : V) (P : List V)
(hP : G.IsShortestPath r x P) (j : ℕ) (hj0 : 0 < j) (hjt : j < P.length - 1) :
G.IsShortestPath r (P[j]'(by omega)) (P.take (j + 1)) ∧
G.IsShortestPath (P[j]'(by omega)) x (P.drop j) := by sorry
end AppliedComb.GraphAlg
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 251, Proposition 12.16
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setup:
- is a weighted digraph on an arbitrary vertex type , not assumed finite. Edge lengths are .
- and are vertices.
- is a list with entries.
- is a shortest path from to :
- is a directed path, meaning , , the entries are pairwise distinct, and each is a directed edge;
- and is at most the corresponding sum for every directed path from to .
- is a natural number with , that is, .
The theorem asserts both of the following.
- The prefix , consisting of the first entries, is a shortest path from to .
- The suffix , obtained by dropping the first entries, is a shortest path from to .
Indices are counted from .
Degenerate cases.
- The hypothesis can hold only when . For no such exists, and the statement is vacuous. This covers:
- , where ;
- a path consisting of a single edge;
- the case , where is truncated to .
- If is unreachable from , no shortest path exists, and the statement is vacuous.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.