Fast point-to-point shortest path computations with arc-flags
Moritz Hilger, Ekkehard A. Köhler, Rolf H. Möhring, Heiko Schilling · DIMACS series in discrete mathematics and theoretical computer science · 2009
We present a number of improvements of the basic variant of the arc-flag acceleration (Lauther, 1997(Lauther, , 2004) ) for point-to-point (P2P) shortest path computations on large graphs.Arc-flags are a modification to the standard Dijkstra algorithm and are used to avoid exploring unnecessary paths during shortest path computation.We assume that for the same input graph the shortest path problem has to be solved repeatedly for different node pairs.Thus, precomputing the arc-flags is possible.We show that the improved arc-flag acceleration achieves speedups of P2P shortest path queries of more than 1,470 on a subnetwork of the German road network 1 with 1M node and 2.5M arcs using 450 bits of additional information per arc.The acceleration factors increase with the size of the input graph.Finally, we present an improved preprocessing version which allows precomputing arc-flags for European and North-American road networks within hours.