Faster algorithms for the shortest path problem

Faster algorithms for the shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor1995714
Country: United States
Volume: 37
Issue: 2
Start Page Number: 213
End Page Number: 223
Publication Date: Apr 1990
Journal: Journal of the Association for Computing Machinery
Authors: , , ,
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 equ1. A two-level form of radix heap gives a bound of equ2. A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of equ3. The best previously known bounds are equ4 using Fibonacci heaps alone and equ5 using the priority queue structure of Van Emde Boas et al.

Reviews

Required fields are marked *. Your email address will not be published.