Distributed approximation algorithms for weighted shortest paths

A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O(log n) bandwidth restriction on edges (the standard synchronous CONGEST model). In this problem every node wants to know its distance to some others nodes. The question whether approximation algorithms help speed up the shortest paths computation (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (SSSP) and all-pairs shortest paths (APSP) in the weighted case. Our main result is an algorithm for SSSP. Previous results are the classic O(n)-time Bellman-Ford algorithm and an Õ(n1/2+1/2k + D)-time (8kdlog(k + 1)e − 1)-approximation algorithm, for any integer k ≥ 1, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use Õ(·) to hide th