Home | english  | Impressum | Sitemap | KIT

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

Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm
Autor:

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

Links:
Quelle:

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.