2005 · 728 citations · 27 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryOptimizationGraph AlgorithmsGraph TheoryHeuristic SearchNetwork OptimizationRouting AlgorithmsShortest Path AlgorithmsShortest Path In Directed GraphsShortest Path On Road NetworksShortest Path ProblemsShortest Paths
We study the problem of finding a shortest path between two vertices in a directed graph. This is an important problem with many applications, including that of computing driving directions. We allow preprocessing the graph using a linear amount of extra space to store auxiliary information, and using this information to answer shortest path queries quickly. Our approach uses A ∗ search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. We also develop new bidirectional variants of A ∗ search and investigate several variants of the new algorithms to find those that are most efficient in practice. Our algorithms compute optimal shortest paths and work on any directed graph. We give experimental results showing that the most efficient of our new algorithms outperforms previous algorithms, in particular A ∗ search with Euclidean bounds, by a wide margin on road networks. We also experiment with several synthetic graph families.
27
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations