New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths
share
We consider the problem of computing all pairs shortest paths (APSP) and shortest paths for k sources in a weighted graph in the distributed CONGEST model. For graphs with non-negative integer edge weights (including zero weights) we build on a recent pipelined algorithm to obtain Õ(λ^1/4· n^5/4) in graphs with non-negative integer edge-weight at most λ, and Õ(n ·^1/3) rounds for shortest path distances at most . Additionally, we simplify some of the procedures in the earlier APSP algorithms for non-negative edge weights in [HNS17,ARKP18]. We also present results for computing h-hop shortest paths and shortest paths from k given sources. In other results, we present a randomized exact APSP algorithm for graphs with arbitrary edge weights that runs in Õ(n^4/3) rounds w.h.p. in n, which improves the previous best Õ(n^3/2) bound, which is deterministic. We also present an Õ(n/ϵ^2)-round deterministic (1+ϵ) approximation algorithm for graphs with non-negative poly(n) integer weights (including zero edge-weights), improving results in [Nanongkai14,LP15] that hold only for positive integer weights.
READ FULL TEXT