Faster Deterministic All Pairs Shortest Paths in Congest Model
Udit Agarwal, Vijaya Ramachandran · 2020
We present a new deterministic algorithm for distributed weighted all pairs shortest paths (APSP) in both undirected and directed graphs. Our algorithm runs in ~O(n4/3 ) rounds in the Congest models on graphs with arbitrary edge weights, and it improves on the previous ~O(n3/2) bound of Agarwal et al. [ARKP18]. The main components of our new algorithm are a new faster technique for constructing blocker set deterministically and a new pipelined method for deterministically propagating distance values from source nodes to the blocker set nodes in the network. Both of these techniques have potential applications to other distributed algorithms.