A Faster Shortest Path Algorithm

A new deterministic algorithm, C-HD, was formally verified in Lean to compute exact shortest-path distances in directed graphs with non-negative real weights. C-HD performs bounded local searches on sorted outgoing-edge lists, limiting repeated work and achieving a certified runtime of \(O(n + m + m\log 2)\) within a specified density range. For graphs outside this range or with few edges, the algorithm falls back to Bellman-Ford, guaranteeing correct results in all cases.