Our main result is a simple randomized algorithm that for any parameter $c>1$ has a worst-case update time of $ O (cn^{2+2/3} \log^{4/3}{n}) $ and answers distance queries correctly with probability $1-1/n^c$, against an adaptive online adversary if the graph contains no negative cycle. The best deterministic algorithm is by Thorup [STOC 2005] with a worst-case update time of $ \tilde O (n^{2+3/4})$ and assumes non-negative weights. This is the first improvement for this problem for more than a decade. Conceptually, our algorithm shows that randomization along with a more direct approach can provide better bounds.
Joint work with Ittai Abraham and Shiri Chechik
To appear in SODA 2017
Preprint: https://arxiv.org/abs/1607.05132