























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^{1+o(1)}\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].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。