A Parallelization of {D}ijkstra's Shortest Path Algorithm

The single source shortest path (SSSP) problem lacks parallel solutions which are fast and simultaneously work-efficient. We propose simple criteria which divide Dijkstra's sequential SSSP algorithm into a number of phases, such that the operations within a phase can be done in parallel. We give a PRAM algorithm based on these criteria and analyze its performance on random digraphs with random edge weights uniformly distributed in $[0,1]$. We use the ${\cal G}(n,d/n)$ model: the graph consists of $n$~nodes and each edge is chosen with probability $d/n$. Our PRAM algorithm needs ${\cal O}(n^{1/3} \log n)$ time and ${\cal O}(n \log n+dn)$ work with high probability (whp). We also give extensions to external memory computation. Simulations show the applicability of our approach even on non-random graphs