### Combining speed-up techniques for shortest-path computationsCombining speed-up techniques for shortest-path computations

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

Source: ACM Digital Library