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

Опубликовано 7 сентября 2016, 17:04

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.