We introduce a formalized mathematical bridge between deterministic graph theory and robust optimization. By applying principlesof interval arithmetic to Johnson’s reweighting algorithm for sparsegraphs, we demonstrate that shortest path optimality is strictly preserved under bounded uncertainty. Natively incorporating the BellmanFord invariant to handle negative edge weights, we explicitly define deterministic robust intervals. The theorems have been machine-verifiedin Lean 4
Sergio Alarcón Rodríguez (Fri,) studied this question.