Faster Algorithms for the Shortest Path Problem
Report ID: TR-154-88Author: Ahuja, Ravindra K. / Mehlhorn, Kurt / Orlin, James B. / Tarjan, Robert E.
Date: 1988-03-00
Pages: 16
Download Formats: |PDF|
Abstract:
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 + n log C). A two-level form of redistributive heap gives a bound of O(m+n log C/log log C). A combination of a redistributive heap and a previously known data structure called a Fibonacci heap gives a bound of O(m+n sqrtlog 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, Kaas and Zijlstra.