Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Computing the Shortest Path: A* Search Meets Graph Theory

A. V. Goldberg and C. Harrelson

Abstract

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.

Details

Publication typeTechReport
URLhttp://www.avglab.com/andrew/pub/siam05.html
NumberMSR-TR-2004-24
Pages25
InstitutionMicrosoft Research
AddressVancouver, Canada
> Publications > Computing the Shortest Path: A* Search Meets Graph Theory