Accession Number : ADA194031

Title :   Faster Algorithms for the Shortest Path Problem,

Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE

Personal Author(s) : Ahuja, Ravindra K ; Mehlhorn, Kurt ; Orlin, James B ; Tarjan, Robert E

PDF Url : ADA194031

Report Date : Mar 1988

Pagination or Media Count : 17

Abstract : This document investigates efficient implementations of Dijkstra's shortest path algorithm. The authors 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 give a time bound of Dijkstra's algorithm of O(m + n log C). A two-level form of redistributive heap give 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 square root of (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, Kaas, and Zijlstra.

Descriptors :   *ALGORITHMS, *PATHS, EDGES, TIME, LOW COSTS, QUEUEING THEORY

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE