A Faster Deterministic Distributed Algorithm for Weighted APSP Through Pipelining
share
We present a new approach to computing all pairs shortest paths (APSP) in a weighted directed graph in the Congest model in the distributed setting. Our approach gives a simple but nontrivial deterministic distributed APSP algorithm that runs in Õ(n^3/2) rounds. This bound matches a recent deterministic distributed algorithm in [ARKP18]. We then combine our new distributed APSP algorithm with a modified version of the algorithm in [ARKP18] to obtain an Õ(n^4/3) round deterministic distributed APSP algorithm in the Congest model, improving the previous best bound of Õ(n^3/2) rounds. We have a similar improvement in the bound for the problem of computing shortest path trees for k given sources. For this latter problem our deterministic distributed algorithm runs in Õ(n · k^1/3) rounds. Our new approach in the Õ(n^3/2) round APSP algorithm is a pipelined strategy that computes each stage of Gabow's scaling algorithm in less than 2n^3/2 + 2n rounds. While this algorithm has a simple description, it has some novel features and a nontrivial analysis.
READ FULL TEXT