TY  - RPRT
T1  - Faster algorithms for the shortest path problem
T3  - Kaiserslautern ; Saarbrücken : DFKI, 1988
A1  - Ahuja,Ravindra K.
A1  - Mehlhorn,Kurt
A1  - Orlin,James B.
A1  - Tarjan,Robert E.
Y1  - 2011/09/06
N2  - We investigate efficient implementations of Dijkstra's shortest path algorithm. We propose a new data structure, called the redistributive heap, 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 redistributive heap gives a time bound for Dijkstra's algorithm of O(m + nlogC). A two-level form of redistributive heap gives a bound of O(m + nlogC/loglogC). A combination of a redistributive heap and a previously known data structure called a Fibonacci heap gives a bound of O(m+ nsqrt{log C}). The best previously known bounds are O(m + nlogn) using Fibonacci heaps alone and O(mloglogC) using the priority queue structure of Van Emde Boas, Kaas, and Zijlstra.
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/4196
ER  -