An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags
Ulrich Lauther · DIMACS series in discrete mathematics and theoretical computer science · 2009
We present an efficient algorithm for fast and exact calculation of shortest paths in graphs with geometrical information in nodes (coordinates), e.g. road networks. The method is based on preprocessing and therefore best suited for static graphs, i.e., graphs with fixed topology and edge costs. In the preprocessing phase, the network is divided into regions and edge flags are calculated that indicate whether an edge belongs to a shortest path into a given region. In the path calculation step, only those edges need to be investigated that carry the appropriate flag. We compared this method to a classical Dijksta implementation using USA road networks with travel times and report on speedup, preprocessing time, and memory needed to store edge flags.