Seminario Interdipartimentale di Algoritmica  

Monday, March 20, 2006, 12:00 noon
Reach for A*: an Efficient Point-to-Point Shortest Path Algorithm
Andrew Goldberg, Microsoft Research

DIS - Department of Computer and System Sciences
Room C3, second floor

Abstract:

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman in several ways. In particular, we add shortcut arcs which reduce vertex reaches. Our modifications greatly reduce both preprocessing and query times. The resulting algorithm is as fast as the best previous method, due to  Sanders and Schultes. However, our algorithm is simpler and combines in a natural way with A* search, which yields significantly better query times. The resulting algorithms are practical for a wide range of platforms, from servers to hand-held devices.

Joint work with Renato Werneck, Princeton University.