Computing Point-to-Point Shortest Paths from External Memory, with A. V. Goldberg. Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments (ALENEX'05), Vancouver, Canada, 2005. Copyright SIAM.

Abstract: We study the ALT algorithm [Goldberg and Harrelson, 2004] for the point-to-point shortest path problem in the context of road networks. We suggest improvements to the algorithm itself and to its preprocessing stage. We also develop a memory-efficient implementation of the algorithm that runs on a Pocket PC. It stores graph data in a flash memory card and uses RAM to store information only for the part of the graph visited by the current shortest path computation. The implementation works even on very large graphs, including that of the North America road network, with almost 30 million vertices.