Overview

The problem of finding shortest paths in graphs is a fundamental optimization problem with many applications. The problem has several variants. Algorithms with near-optimal efficiency, either in theory or in practice, are known for some problem variants, such as the single-source problem. For other variants, significant improvement over the current state of the art may be possible.

A significant effort ofthe SPA projectis devoted to the following variant of the shortest path problem. Given a graph, we preprocess it subject to the restriction that the space for the preprocessing results is limited (e.g., a small constant times the space used to store the graph). Then we would like to quickly answer queries on single-pair shortest paths. This is a natural variant of the problem as in many applications, such as that of computing driving directions (e.g., Google Maps, Yahoo! Maps, Live Search Maps).

We developed several techniques for speeding up classical algorithms for the problem. These include landmark-based A* search, reach-based pruning, and their combinations. The resulting algorithms are very practical and can be used on servers, desktops, or portable devices (e.g., car navigation systems). Some of these algorithms are being used by Live Search Maps.

Other problems we have studied include shortest path feasibility and minimum cycle mean problems. Our research lead to better understanding the practical performance of existing algorithms and the development of new algorithms with good practical performance.

Additional details about our results can be found in project publications.

Project Visitors

• Boris V. Cherkassky
• Chris Harrelson
• Haim Kaplan