ALCOMFT-TR-01-95

Ulrich Meyer and Peter Sanders
Parallel Shortest Path for Arbitrary Graphs
MPI. Work packages 1 and 2. May 2001.

Abstract: In spite of intensive research, no work-efficient parallel algorithm for the single source shortest path problem is known which works in sublinear time for arbitrary directed graphs with non-negative edge weights. We present an algorithm that improves this situation for graphs where the ratio \Diam/\Delta between the maximum weight of a shortest path \Diam and a ``safe step width'' \Delta is not too large. We show how such a step width can be found efficiently and give several graph classes which meet the above condition, such that our parallel shortest path algorithm runs in sublinear time and uses linear work. The new algorithm is even faster than a previous one which only works for random graphs with random edge weights [MeySan98a]. On those graphs our new approach is faster by a factor of \Thlog n/loglog n and achieves an expected time bound of \Ohlog² n using linear work.

Postscript file: ALCOMFT-TR-01-95.ps.gz (96 kb).