We study the problem of finding a shortest path between two given
vertices in a directed graph. This is an important problem with many
applications, including that of computing driving directions.
We are interested in preprocessing the graph using a linear
amount of extra space to store additional information,
and using this information to answer shortest paths queries quickly.
We use A* search in combination with new distance lower-bounding
techniques based on landmarks and triangle inequality. Our experiments
show that on some graph classes, such as map graphs, the new algorithm
works very well. In particular, we are able to solve the problem
on the graph of North America road networks with 30 million vertices
on a handheld device. In this talk we describe the algorithm, its
implementation, and experimental performance.

Joint work with Chris Harrelson and Renato Werneck