Reach for A*: an Efficient Point-to-Point Shortest Path Algorithm

1,069 views · Published 7 September 2016 · 1:07:00 · Indexed 8 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We consider two approaches to the problem.     The classical A* search directs the search towards the goal. A recent reach-based approach of Gutman identifies local vertices during preprocessing, which allows it to prune these vertices during searches.   These approaches can be combined, resulting in further reduction of the search space.    We discuss efficient implementations of these approaches and their combination. The resulting algorithms are quite practical for our motivating application, computing driving directions, both for server and for portable device applications.

More from this channel