Heuristic Search and Triangle Inequality

We study the problem of finding a shortest path between two vertices in a directed graph. This is an important problem with many applications, including that of computing driving directions, our motivating one. We allow preprocessing the graph using a linear (in the graph size) amount of extra space to store additional information. This information helps us to answer shortest paths queries quickly. Our main contribution is a new distance lower-bounding technique hat, combined with heuristic search (aka A* search), gives surprisingly good results for important classes of graphs. The this technique is based on landmarks and triangle inequality. We also study several bidirectional variants of heuristic search,including new variants. Computational experiments show that on some graph classes,in particular road networks, these algorithms work very well. This talk is aimed at a general Computer Science audience. Joint work with Chris Harrelson