Faster algorithms for the shortest path problem
- 1 April 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 37 (2), 213-223
- https://doi.org/10.1145/77600.77615
Abstract
Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap , is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C , a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O ( m + n log C ). A two-level form of radix heap gives a bound of O ( m + n log C /log log C ). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O ( m + n a @@@@log C ). The best previously known bounds are O ( m + n log n ) using Fibonacci heaps alone and O ( m log log C ) using the priority queue structure of Van Emde Boas et al. [ 17].Keywords
This publication has 13 references indexed in Scilit:
- Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computationCommunications of the ACM, 1988
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- SortingPublished by Springer Science and Business Media LLC ,1984
- Storing a sparse tableCommunications of the ACM, 1979
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Preserving order in a forest in less than logarithmic time and linear spaceInformation Processing Letters, 1977
- Efficient Algorithms for Shortest Paths in Sparse NetworksJournal of the ACM, 1977
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976
- Algorithm 360: shortest-path forest with topological ordering [H]Communications of the ACM, 1969
- A note on two problems in connexion with graphsNumerische Mathematik, 1959