Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
Reinhard Bauer, Daniel Delling, Peter W. Sanders, Dennis Schieferdecker, Dominik Schultes, Dorothea Wagner · ACM Journal of Experimental Algorithmics · 2010
In recent years, highly effective hierarchical and goal-directed speed-up techniques for routing in large road networks have been developed. This article 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.