Computing the shortest path: A search meets graph theory

ABSTRACT

We propose shortest path algorithms that use A* search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. Our algorithms compute optimal shortest paths and work on any directed graph. We give experimental results showing that the most efficient of our new algorithms outperforms previous algorithms, in particular A* search with Euclidean bounds, by a wide margin on road networks and on some synthetic problem families.

REFERENCES

• 1: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.516-525, January 23-25, 1994, Arlington, Virginia, United States
• 2: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 3: Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.51-59, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343516]
• 4: G. B. Dantzig. Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1962.
• 5: Dennis de Champeaux, Bidirectional Heuristic Search Again, Journal of the ACM (JACM), v.30 n.1, p.22-32, Jan. 1983 [doi>10.1145/322358.322360]
• 6: E. V. Denardo and B. L. Fox. Shortest-Route Methods: 1. Reaching, Pruning, and Buckets. Oper. Res., 27:161--186, 1979.
• 7: E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math., 1:269--271, 1959.
• 8: J. Doran. An Approach to Automatic Problem-Solving. Machine Intelligence, 1:105--127, 1967.
• 9: D. Dreyfus. An Appraisal of Some Shortest Path Algorithms. Technical Report RM-5433, Rand Corporation, Santa Monica, CA, 1967.
• 10: J. Fakcharoenphol, Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.232, October 14-17, 2001
• 11: L. Ford, Jr. Network Flow Theory. Technical Report P-932, The Rand Corporation, 1956.
• 12: L. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962.
• 13: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 14: G. Gallo and S. Pallottino. Shortest Paths Algorithms. Annals of Oper. Res., 13:3--79, 1988.
• 15: A. Goldberg and C. Harrelson. Computing the Shortest Path: A* Search Meets Graph Theory. Technical Report MSR-TR-2004-24, Microsoft Research, 2004.
• 16: Andrew V. Goldberg, A Simple Shortest Path Algorithm with Linear Average Time, Proceedings of the 9th Annual European Symposium on Algorithms, p.230-241, August 28-31, 2001
• 17: Andrew V. Goldberg, Shortest Path Algorithms: Engineering Aspects, Proceedings of the 12th International Symposium on Algorithms and Computation, p.502-513, December 19-21, 2001
• 18: A. V. Goldberg and C. Silverstein. Implementations of Dijkstra's Algorithm Based on Multi-Level Buckets. In P. M. Pardalos, D. W. Hearn, and W. W. Hages, editors, Lecture Notes in Economics and Mathematical Systems 450 (Refereed Proceedings), pages 292--327. Springer Verlag, 1997.
• 19: R. Gutman. Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In Proc. 6th International Workshop on Algorithm Engineering and Experiments, pages 100--111, 2004.
• 20: P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on System Science and Cybernetics, SSC-4(2), 1968.
• 21: T. Ikeda, M.-Y. Hsu, H. Imai, S. Nishimura, H. Shimoura, T. Hashimoto, K. Tenmoku, and K. Mitoh. A Fast Algorithm for Finding Better Routes by AI Search Techniques. In Proc. Vehicle Navigation and Information Systems Conference. IEEE, 1994.
• 22: R. Jacob, M. Marathe, and K. Nagel. A Computational Study of Routing Algorithms for Realistic Transportation Networks. Oper. Res., 10:476--499, 1962.
• 23: Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.820-827, January 06-08, 2002, San Francisco, California
• 24: James B.H. Kwa, BS*: an admissible bidirectional staged heuristic search algorithm, Artificial Intelligence, v.38 n.1, p.95-109, Feb. 1989 [doi>10.1016/0004-3702(89)90069-6]
• 25: Ulrich Meyer, Single-source shortest-paths on arbitrary directed graphs in linear average-case time, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.797-806, January 07-09, 2001, Washington, D.C., United States
• 26: T. A. J. Nicholson. Finding the Shortest Route Between Two Points in a Network. Computer J., 9:275--280, 1966.
• 27: I. Pohl. Bi-directional Search. In Machine Intelligence, volume 6, pages 124--140. Edinburgh Univ. Press, Edinburgh, 1971.
• 28: Frank Schulz , Dorothea Wagner , Christos D. Zaroliagis, Using Multi-level Graphs for Timetable Information in Railway Systems, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.43-59, January 04-05, 2002
• 29: Robert Sedgewick , Jeffrey Scott Vitter, Shortest paths in Euclidean graphs, Algorithmica, v.1 n.1, p.31-48, Jan. 1986 [doi>10.1007/BF01840435]
• 30: Lenie Sint , Dennis de Champeaux, An Improved Bidirectional Heuristic Search Algorithm, Journal of the ACM (JACM), v.24 n.2, p.177-191, April 1977 [doi>10.1145/322003.322004]
• 31: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 32: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 33: M. Thorup, Compact Oracles for Reachability and Approximate Distances in Planar Digraphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.242, October 14-17, 2001
• 34: D. Wagner and T. Willhalm. Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs. In European Symposium on Algorithms, 2003.
• 35: F. Benjamin Zhan , Charles E. Noon, Shortest Path Algorithms: An Evaluation Using Real Road Networks, Transportation Science, v.32 n.1, p.65-73, January 1998 [doi>10.1287/trsc.32.1.65]
• 36: F. B. Zhan and C. E. Noon. A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Paths. Journal of Geographic Information and Decision Analysis, 4, 2000.