Title
Acceleration of Shortest Path Computation
Authors
-
Source
-
Classification
-
| MSC: |
| primary: | 05C85 | Graph algorithms |
| secondary: | 05C20 | Directed graphs , tournaments |
| 90B20 | Traffic problems |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics |
Keywords
-
shortest path, constrained shortest path, Dijkstra's algorithm, acceleration method, road network
-
-
The paper reports on an empirical study on acceleration methods for single
source single target shortest path computations based on Dijkstra's algorithm
and a generalized version of it for constrained shortest paths. In particular,
for the common shortest path case we investigate the hierarchical separator and
the so-called arc-flag approaches. For the constrained shortest path case we
discuss the goal-directed and bi-directed approaches. Furthermore, we look at
appropriate combinations of these methods. For shortest paths divide and conquer
seem to yield a significant speed-up. In this approach a small number of node
separators divide the graph into regions of ideally balanced size. A
preprocessing phase gathers information in order to facilitate the search for
shortest paths that stretch over several regions. Greater accelerations are
achieved by an arc labeling approach that is based on a
partition of the graph into regions and marks every arc with a vector of
bit-flags storing information on whether or not that arc is on a shortest path
into one of the regions. A combination of an appropriate partition with a
bi-directed search constantly yields significant speed-ups on the average, e.g.
by a factor between 700 and 1100 on parts of the German road network. In many
cases the search space of Dijkstra's algorithm is narrowed down to the size of
the shortest path itself. For the constrained shortest path problem we show that
standard acceleration methods can be applied. Here, the simple goal-directed
search yields the best speed-up and the bi-directed search which does not need
preprocessing compares favourably to it.
