Thumbnail
Access Restriction
Subscribed

Author Holzer, Martin ♦ Schulz, Frank ♦ Wagner, Dorothea ♦ Willhalm, Thomas
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Dijkstra's algorithm ♦ Shortest path ♦ Combination ♦ Speed-up
Abstract In practice, computing a shortest path from one node to another in a directed graph is a very common task. This problem is classically solved by Dijkstra's algorithm. Many techniques are known to speed up this algorithm heuristically, while optimality of the solution can still be guaranteed. In most studies, such techniques are considered individually. The focus of our work is $\textit{combination}$ of speed-up techniques for Dijkstra's algorithm. We consider all possible combinations of four known techniques, namely, goal-directed search, bidirectional search, multilevel approach, and shortest-path containers, and show how these can be implemented. In an extensive experimental study, we compare the performance of the various combinations and analyze how the techniques harmonize when jointly applied. Several real-world graphs from road maps and public transport and three types of generated random graphs are taken into account.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 10


Open content in new tab

   Open content in new tab
Source: ACM Digital Library