# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### A Parallelization of Dijkstra's Shortest Path Algorithm

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Crauser, A., Mehlhorn, K., Meyer, U., & Sanders, P. (1998). A Parallelization of
Dijkstra's Shortest Path Algorithm. In L. Brim, J. Gruska, & J. Zlatuška (*Mathematical Foundations of Computer Science 1998 * (pp. 722-731). Berlin, Germany: Springer.
doi:10.1007/BFb0055823.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-372F-7

##### Abstract

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.