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 irections. We allow preprocessing the graph using a linear amount of xtra 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.

PostScript file

PDF file

In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05)

Details