$\Delta$-Stepping: A Parallel Single Source Shortest Path Algorithm

In spite of intensive research, little progress has been made towards fast and work-efficient parallel algorithms for the single source shortest path problem. Our \emph{$\Delta$-stepping algorithm}, a generalization of Dial's algorithm and the Bellman-Ford algorithm, improves this situation at least in the following ``average-case'' sense: For random directed graphs with edge probability $\frac{d}{n}$ and uniformly distributed edge weights a PRAM version works in expected time ${\cal O}(\log^3 n/\log\log n)$ using linear work. The algorithm also allows for efficient adaptation to distributed memory machines. Implementations show that our approach works on real machines. As a side effect, we get a simple linear time sequential algorithm for a large class of not necessarily random directed graphs with random edge weights