Undirected single-source shortest paths with positive integer weights in linear time
- 1 May 1999
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 46 (3) , 362-394
- https://doi.org/10.1145/316542.316548
Abstract
The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s , find the shortest path from s to all other vertices in the graph. Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from s . Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from s . However, we do not know how to sort in linear time. Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.Keywords
This publication has 15 references indexed in Scilit:
- Fusion trees can be implemented with AC0 instructions onlyTheoretical Computer Science, 1999
- Faster Shortest-Path Algorithms for Planar GraphsJournal of Computer and System Sciences, 1997
- Improved Parallel Integer Sorting without Concurrent WritingInformation and Computation, 1997
- Trans-dichotomous algorithms for minimum spanning trees and shortest pathsJournal of Computer and System Sciences, 1994
- Surpassing the information theoretic bound with fusion treesJournal of Computer and System Sciences, 1993
- Faster algorithms for the shortest path problemJournal of the ACM, 1990
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956