Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm
Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, Dorothea Wagner
ACM Journal of Experimental Algorithmics, Volume 15, 2010
In recent years, highly effective hierarchical and goal-directed speedup techniques for routing in large road networks have been developed. This paper makes a systematic study of combinations of such techniques. These combinations turn out to give the best results in many scenarios, including graphs for unit disk graphs, grid networks, and time-expanded timetables. Besides these quantitative results, we obtain general insights for successful combinations.