Computing the Shortest Path: A* Search Meets Graph Theory

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.

soda05.pdf
PDF file

In  Proc. ACM_SIAM Symp. on Discrete Algorithms

Publisher  ACM
ACM

Details

TypeInproceedings
> Publications > Computing the Shortest Path: A* Search Meets Graph Theory