International Workshop on Experimental Algorithms (WEA 2008)

Provincetown, MA, USA

Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, Dorothea Wagner

In [1], basic speed-up techniques for Dijkstra's algorithm have been combined. The key observation in their 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.

2008

• PDF