A Faster Distributed Single-Source Shortest Paths Algorithm

Sebastian Krinninger, Danupon Nanongkai

Published 2017-11-03Version 1

We devise new algorithms for the single-source shortest paths problem in the CONGEST model of distributed computing. While close-to-optimal solutions, in terms of the number of rounds spent by the algorithm, have recently been developed for computing single-source shortest paths approximately, the fastest known exact algorithms are still far away from matching the lower bound of $ \tilde \Omega (\sqrt{n} + D) $ rounds by Peleg and Rubinovich [SICOMP'00], where $ n $~is the number of nodes in the network and $ D $ is its diameter. The state of the art is Elkin's randomized algorithm [STOC'17] that performs $ \tilde O(n^{2/3} D^{1/3} + n^{5/6}) $ rounds. We significantly improve upon this upper bound with our two new randomized algorithms, the first performing $ \tilde O (\sqrt{n D}) $ rounds and the second performing $ \tilde O (\sqrt{n} D^{1/4} + n^{3/5} + D) $ rounds.