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

Meyer, Ulrich; Sanders, Peter

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

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

MPS-Authors

/persons/resource/persons45038

Meyer, Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45344

Sanders, Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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 (Eds.), 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.