Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

Liam Roditty, Ariel Sapir

We present a $+2{\sum }_{i=1}^{k+1}{W}_i$-APASP algorithm for dense weighted graphs with runtime $\tilde{O}\left(n^{2+\frac{1}{3k+2}}\right)$, where $W_i$ is the weight of an $i^{th}…