A Randomized Parallel Algorithm for Single-Source Shortest Paths

We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is based on the technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search.