Fast data structures for shortest path routing: a comparative evaluation

Author

Oberhauser, Glen ; Simha, Rahul

Author_Institution

Alabama Univ., USA

Volume

3

fYear

1995

fDate

18-22 Jun 1995

Firstpage

1597

Abstract

The execution time of Dijkstra´s (1959) algorithm for shortest path routing strongly depends upon the underlying priority queue data structure used to store intermediate path costs for the graph during the algorithm´s iterations. In particular, the efficiency is determined by how quickly the data structure can execute the operations of EXTRACT-MIN and DECREASE-KEY. Using Dijkstra´s algorithm on graphs of various sizes and topologies, this paper compares the actual performance of the standard implicit binary heap with that of several proposed data structures: the binomial heap, relaxed heap, run relaxed heap, Fibonacci heap and splay tree. In particular, we compare the data structures´ performance of the key operations, EXTRACT-MIN and DECREASE-KEY

Keywords

computational geometry; telecommunication network routing; tree data structures; Dijkstra´s algorithm; Fibonacci heap; binary heap; binomial heap; fast data structures; graph during; intermediate path costs; iterations; performance; priority queue data structure; relaxed heap; run relaxed heap; shortest path routing; splay tree; Computer networks; Costs; Data mining; Data structures; Routing; Software algorithms; Testing; Topology; Tree data structures; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, 1995. ICC '95 Seattle, 'Gateway to Globalization', 1995 IEEE International Conference on

Conference_Location

Seattle, WA

Print_ISBN

0-7803-2486-2

Type

conf

DOI

10.1109/ICC.1995.524471

Filename

524471