A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks…