|
Faster algorithms for the shortest path problem R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, Journal of ACM 37, 213-223, 1990 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 + nm). 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. |