direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 11-2005

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Partitioning Graphs to Speed Up Dijkstra's Algorithm
to appear in Proceedings of WEA 2005.
primary: 05C85 Graph algorithms
secondary: 05C20 Directed graphs , tournaments
90B20 Traffic problems
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics
not available
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.
Download as [PDF] [ps.gz] [ps]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe