Estimativa Robusta de Intervalos e Limites de Acúmulo de Erros em Algoritmos de Caminho Mais Curto via Reponderação de Johnson

Introduzimos uma ponte matemática formalizada entre a teoria dos grafos determinística e a otimização robusta sob incerteza estocástica. Ao aplicar princípios da aritmética de intervalos ao algoritmo de reponderação de Johnson para grafos esparsos, demonstramos que a otimalidade do caminho mais curto é estritamente preservada sob incerteza limitada. Avançando além da preservação trivial da largura, estabelecemos limites matematicamente verificados para o acúmulo de erros do caminho, provando que intervalos robustos determinísticos mantêm uma variância aditiva estritamente linear. Além disso, provamos que potenciais heurísticos arbitrários derivados da cota assintótica inferior garantem validade topológica em todo o espectro de incerteza. Os teoremas foram verificados por máquina nativamente no Lean 4 sem declarações omitidas.