Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method

We give an algorithm that takes a directed graph G undergoing m edge insertions with lengths in $[1, W]$, and maintains $(1+ε)$-approximate shortest path distances from a fixed source s to all other vertices. The algorithm is deterministic and runs in total time m¹⁺ᵒ⁽¹⁾log W, for any ε> exp(-(log m)0.99). This is achieved by designing a nonstandard interior point method to crudely detect when the distances from s other vertices v have decreased by a $(1+ε)$ factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024].