Distributed Weighted All Pairs Shortest Paths Through Pipelining
Udit Agarwal, Vijaya Ramachandran · 2019
We present new results for the distributed computation of all pairs shortest paths (APSP) in the CONGEST model in an n-node graph with moderate non-negative integer weights. Our methods can handle zero-weight edges which are known to present difficulties for distributed APSP algorithms. The current best deterministic distributed algorithm in the CONGEST model that handles zero weight edges is the Õ(n3/2)-round algorithm of Agarwal et al. [3] that works for arbitrary edge weights. Our new deterministic algorithms run in O(W1/4· n5/4) rounds in graphs with non-negative integer edge-weight at most W, and in Õ(n·Δ1/3) rounds for shortest path distances at most Δ. These algorithms are built on top of a new pipelined algorithm we present for this problem that runs in at most 2n√Δ + 2n rounds. Additionally, we show that the techniques in our results simplify some of the procedures in the earlier APSP algorithms for non-negative edge weights in [3], [13]. We also present new results for computing h-hop shortest paths from k given sources, including the notion of consistent h-hop shortest path trees, and we present an O(n/ϵ2)-round deterministic (1+ϵ) approximation algorithm for graphs with non-negative poly(n) integer weights, improving results in [16], [18] that hold only for positive integer weights.