direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2005

Partitioning Graphs to Speed Up Dijkstra's Algorithm
Zitatschlüssel Report-011-2005
Autor Rolf H. Möhring and Heiko Schilling and Birk Schütz and Dorothea Wagner and Thomas Willhalm
Jahr 2005
Adresse Straße des 17. Juni 136, 10623 Berlin
Nummer 011
Monat April
Notiz to appear in Proceedings of WEA 2005.
Institution TU Berlin
Zusammenfassung In this paper, we consider Dijkstra's algorithm for the point-to-point shortest path problem in large and sparse graphs with a given layout. Lauther presented a method that uses a partitioning of the graph to perform a preprocessing which allows to speed-up Dijkstra's algorithm considerably. We present an experimental study that evaluates which partitioning methods are suited for this approach. In particular, we examine partitioning algorithms from computational geometry and compare their impact on the speed-up of the shortest-path algorithm. Using a suited partitioning algorithm speed-up factors of 500 and more were achieved. Furthermore, we present an extension of this speed-up technique to multiple levels of partitionings. With this multi-level variant, the same speed-up factors can be achieved with smaller space requirements. It can therefore be seen as a compression of the precomputed data that conserves the correctness of the computed shortest paths.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag