Buckets strike back: improved parallel shortest-paths
Ulrich Meyer · 2002
We study the average-case complexity of the parallel single-source shortest path (SSSP) problem, assuming arbitrary directed graphs with n nodes, m edges, and independent random edge weights uniformly distributed in [0, 1]. We provide a new bucket-based parallel SSSP algorithm that runs in T=O(log2n·mini{2i·L+|Vi|}) average-case time using O(n+m+T) work on a PRAM, where L denotes the maximum shortest-path weight and |Vi| is the number of graph vertices with in-degree at least 2i. All previous algorithms either required more time or more work. The minimum performance gain is a logarithmic factor improvement; on certain graph classes, accelerations by factors of more than n0.4can be achieved. The algorithm also allows adaptation to distributed memory machines.