Computing the Shortest Path: A* Search Meets Graph Theory

Andrew V. Goldberg and Chris Harrelson

Abstract

We propose shortest path algorithms that use A* search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. Our algorithms compute optimal shortest paths and work on any directed graph. We give experimental results showing that the most eĀ±cient of our new algorithms outperforms previous algorithms, in particular A* search with Euclidean bounds, by a wide margin on road networks and on some synthetic problem families.

Details

Publication typeInproceedings
Published inProc. ACM_SIAM Symp. on Discrete Algorithms
PublisherACM
> Publications > Computing the Shortest Path: A* Search Meets Graph Theory