# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Meyer, U., & Sanders, P. (1998). $\Delta$-Stepping: A Parallel Single Source Shortest
Path Algorithm. In G. Bilardi, G. F. Italiano, A. Pietracaprina, & G. Pucci (*Proceedings of the 6th Annual European Symposium on Algorithms (ESA-98)* (pp. 393-404).
Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-377B-C

##### Abstract

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.