Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde{O}(n^{5/4})$ Rounds

Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak

We study computing {\em all-pairs shortest paths} (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from…