Computing shortest paths is one of the central problems in the theory of distributed computing. For the last few years, substantial progress has been made on the approximate single source shortest paths problem, culminating in an algorithm of Henzinger, Krinninger, and Nanongkai [STOC’16] which deterministically computes (1+o(1))-approximate shortest paths in O(D+√n) time, where D is the hop-diameter of the graph. Up to logarithmic factors, this time complexity is optimal, matching the lower bound of Elkin [STOC’04]. The question of exact shortest paths however saw no algorithmic progress for decades, until the recent breakthrough of Elkin [STOC’17], which established a sublinear-time algorithm for exact single source shortest paths on undirected graphs. Shortly after, [FOCS’17] provided improved algorithms for exact all pairs shortest paths problem on directed graphs. In this paper, we provide an alternative single-source shortest path algorithm with complexity O(n3 4D1 4). For polylogarithmic D, this improves on Elkin’s O(n5 6) bound and gets closer to the Ω(n1 2) lower bound of Elkin [STOC’04]. For larger values of D, we present an improved variant of our algorithm which achieves complexity O(max n3 4+o(1) , n3 4D1 6 + D ), and thus compares favorably with Elkin’s bound of O(max n5 6, n2 3D1 3 + D ) in essentially the entire range of parameters. This algorithm provides also a qualitative improvement, because it works for the more challenging case of directed graph (i.e., graphs where the two directions of an edge can have different weights), constituting the first sublinear-time algorithm for directed graphs. Our algorithm also extends to the case of exact r-source shortest paths, in which we provide the fastest algorithm for moderately small r and D, improving on those of
Despite the numerous steps of progress that brought us to an almost complete understanding of the approximate case of SSSP, computing exact SSSP remained open until very recently. But then came the breakthrough of Elkin @cite_26 , which provided the first sublinear-time algorithm for exact SSSP. More precisely, Elkin gave an algorithm that computes exact SSSP in @math rounds if @math , and in @math rounds if @math .
@cite_26
2592613193
We devise new algorithms for the single-source shortest paths (SSSP) problem with non-negative edge weights 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 SSSP approximately, the fastest known exact algorithms are still far away from matching the lower bound of  (n + D) rounds by Peleg and Rubinovich [SIAM Journal on Computing 2000], 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 2017] that performs O(n^2 3 D^1 3 + n^5 6) rounds. We significantly improve upon this upper bound with our two new randomized algorithms for polynomially bounded integer edge weights, the first performing O(n D) rounds and the second performing O(n D^1 4 + n^3 5 + D) rounds. Our bounds also compare favorably to the independent result by Ghaffari and Li [STOC 2018]. As side results, we obtain a (1+e)-approximation O((n D^1 4+D) e)-round algorithm for directed SSSP and a new work depth trade-off for exact SSSP on directed graphs in the PRAM model.