KIT | KIT-Bibliothek | Impressum | Datenschutz

Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm

Bauer, Reinhard; Delling, Daniel; Sanders, Peter ORCID iD icon; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea

Abstract:

In "Combining Speed-up Techniques for Shortest-Path Computations", basic speed-up techniques for Dijkstra's algorithm have been combined. The key observation in this work was that it is most promising to combine hierarchical and goal-directed speed-up techniques. However, since its publication, impressive progress has been made in the field of speed-up techniques for Dijkstra’s algorithm and huge data sets have been made available.
Hence, we revisit the systematic combination of speed-up techniques in this work, which leads to the fastest known algorithms for various scenarios. Even for road networks, which have been worked on heavily during the last years, we are able to present an improvement in performance. Moreover, we gain interesting insights into the behavior of speed-up techniques when combining them.


Volltext §
DOI: 10.5445/IR/1000014952
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2008
Sprache Englisch
Identifikator ISBN: 978-3-540-68548-7
ISSN: 0302-9743
urn:nbn:de:swb:90-149522
KITopen-ID: 1000014952
Erschienen in Experimental Algorithms. 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30 - June 1, 2008. proceedings Ed.: C.C. McGeoch
Verlag Springer-Verlag
Seiten 303-318
Serie Lecture Notes in Computer Science ; 5038
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page