Shortest-path queries in static networks

Abstract

We consider the point-to-point (approximate) shortest-path query problem, which is the following generalization of the classical single-source (SSSP) and all-pairs shortest-path (APSP) problems: we are first presented with a network (graph). A so-called preprocessing algorithm may compute certain information (a data structure or index) to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance queries, which should be answered as fast as possible.

Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast route planning methods; database and information systems researchers investigate materialization tradeoffs, query processing on spatial networks, and reachability queries; and theoretical computer scientists analyze distance oracles and sparse spanners. Related problems are considered for compact routing and distance labeling schemes in networking and distributed computing and for metric embeddings in geometry as well.

In this survey, we review selected approaches, algorithms, and results on shortest-path queries from these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguable practical significance such as planar graphs and complex networks.

References

1. I. Abraham, Y. Bartal, and O. Neiman. 2008a. Embedding metric spaces in their intrinsic dimension. In 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). 363--372.
2. I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. 2011a. VC-dimension and shortest path algorithms. In 38th International Colloquium on Automata, Languages and Programming (ICALP). 690--699.
3. I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. 2012a. HLDB: location-based services in databases. In SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS). 339--348.
4. I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. 2011b. A hub-based labeling algorithm for shortest paths in road networks. In 10th International Symposium on Experimental Algorithms (SEA). 230--241.
5. I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. 2012b. Hierarchical hub labelings for shortest paths. In 20th European Symposium on Algorithms (ESA). 24--35.
6. I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 782--793.
7. I. Abraham and C. Gavoille. 2006. Object location using path separators. In 25th ACM Symposium on Principles of Distributed Computing (PODC). 188--197.
8. I. Abraham and C. Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In 25th International Symposium on Distributed Computing (DISC). 404--415.
9. I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup. 2008b. Compact name-independent routing with minimum stretch. ACM Transactions on Algorithms 4, 3.
10. D. Achlioptas, A. Clauset, D. Kempe, and C. Moore. 2009. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. Journal of the ACM 56, 4.
11. R. Agarwal. 2013. The space-stretch-time trade-off in distance oracles. Preprint.
12. R. Agarwal, M. Caesar, P. B. Godfrey, and B. Y. Zhao. 2012. Shortest paths in less than a millisecond. In 5th Workshop on Online Social Networks (WOSN).
13. R. Agarwal and P. B. Godfrey. 2013. Distance oracles for stretch less than 2. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). 526--538.
14. R. Agarwal, P. B. Godfrey, and S. Har-Peled. 2011. Approximate distance queries and compact routing in sparse graphs. In 30th IEEE International Conference on Computer Communications (INFOCOM). 1754--1762.
15. R. Agrawal and H. V. Jagadish. 1989. Materialization and incremental update of path information. In 5th International Conference on Data Engineering (ICDE). 374--383.
16. W. Aiello, F. R. K. Chung, and L. Lu. 2000. A random graph model for massive graphs. In 32nd ACM Symposium on Theory of Computing (STOC). 171--180.
17. M. Ajtai and R. Fagin. 1990. Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic 55, 1, 113--150. Announced at FOCS 1988.
18. S. B. Akers. 1960. The use of Wye-Delta transformations in network simplification. Operations Research 8, 3, 311--323. Announced at Rand Symposium on Mathematical Programming 1959.
19. T. Akiba, Y. Iwata, and Y. Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 349--360.
20. T. Akiba, C. Sommer, and K. Kawarabayashi. 2012. Shortest-path queries for complex networks: Exploiting low tree-width outside the core. In 15th International Conference on Extending Database Technology (EDBT). 144--155.
21. N. Alon, P. D. Seymour, and R. Thomas. 1990. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3, 4, 801--808. Announced at STOC 1990.
22. S. R. Arikati, D. Z. Chen, L. P. Chew, G. Das, M. H. M. Smid, and C. D. Zaroliagis. 1996. Planar spanners and approximate shortest path queries among obstacles in the plane. In 4th European Symposium on Algorithms (ESA). 514--528.
23. J. Arz, D. Luxen, and P. Sanders. 2013. Transit node routing reconsidered. In 12th International Symposium on Experimental Algorithms (SEA). 55--66.
24. B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. 1998. Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing 28, 1, 263--277.
25. M. A. Babenko, A. V. Goldberg, A. Gupta, and V. Nagarajan. 2013. Algorithms for hub label optimization. In 40th International Colloquium on Automata, Languages, and Programming (ICALP). 69--80.
26. Z. K. Baker and M. Gokhale. 2007. On the acceleration of shortest path calculations in transportation networks. In 15th IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM). 23--32.
27. C. L. Barrett, K. R. Bisset, R. Jacob, G. Konjevod, and M. V. Marathe. 2002. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. In 10th European Symposium on Algorithms (ESA). 126--138.
28. Y. Bartal, L.-A. Gottlieb, T. Kopelowitz, M. Lewenstein, and L. Roditty. 2011. Fast, precise and dynamic distance queries. In 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 840--853.
29. H. Bast. 2009. Car or public transport—two worlds. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. 355--367.
30. H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. 2007a. In transit to constant time shortest-path queries in road networks. In 9th Workshop on Algorithm Engineering and Experiments (ALENEX).
31. H. Bast, S. Funke, P. Sanders, and D. Schultes. 2007b. Fast routing in road networks with transit nodes. Science 316, 5824, 566.
32. S. Baswana, A. Gaur, S. Sen, and J. Upadhyay. 2008. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In 35th International Colloquium on Automata, Languages and Programming (ICALP). 609--621.
33. S. Baswana and T. Kavitha. 2010. Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM Journal on Computing 39, 7, 2865--2896.
34. S. Baswana and S. Sen. 2006. Approximate distance oracles for unweighted graphs in expected O(n²) time. ACM Transactions on Algorithms 2, 4, 557--577.
35. R. Bauer, T. Columbus, B. Katz, M. Krug, and D. Wagner. 2010a. Preprocessing speed-up techniques is hard. In 7th International Conference on Algorithms and Complexity (CIAC). 359--370.
36. R. Bauer, T. Columbus, I. Rutter, and D. Wagner. 2013. Search-space size in contraction hierarchies. In 40th International Colloquium on Automata, Languages, and Programming (ICALP). 93--104.
37. R. Bauer, G. D'Angelo, D. Delling, and D. Wagner. 2009. The shortcut problem—complexity and approximation. In 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). 105--116.
38. R. Bauer and D. Delling. 2009. SHARC: Fast and robust unidirectional routing. ACM Journal of Experimental Algorithmics 14.
39. R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. 2010b. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. ACM Journal of Experimental Algorithmics 15, 2.3, 1--31.
40. A. Berger, D. Delling, A. Gebhardt, and M. Müller-Hannemann. 2009. Accelerating time-dependent multi-criteria timetable information is harder than expected. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS).
41. J. Boothroyd. 1967. Algorithms: Author's note on algorithms 22, 23, 24. Computer Journal 10, 3, 306--308.
42. J. Bourgain. 1985. On lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics 52, 1--2, 46--52.
43. M. H. Bourgoin and E. M. J. Heurgon. 1969. Study and comparison of algorithms of the shortest path through planned experiments. In Project Planning by Network Analysis. 106--118.
44. A. Brady and L. Cowen. 2006. Compact routing on power law graphs with additive stretch. In 8th Workshop on Algorithm Engineering and Experiments (ALENEX). 119--128.
45. E. Brunel, D. Delling, A. Gemsa, and D. Wagner. 2010. Space-efficient SHARC-routing. In 9th International Symposium on Experimental Algorithms (SEA). 47--58.
46. F. Buchholz. 2000. Hierarchische Graphen zur Wegesuche. Ph.D. thesis, Universität Stuttgart.
47. F. Buchholz and B. Riedhofer. 1997. Hierarchische Graphen zur kürzesten Wegesuche in planaren Graphen. Tech. rep. 13, Universität Stuttgart.
48. V. Bulitko, Y. Björnsson, N. R. Sturtevant, and R. Lawrence. 2010. Real-time heuristic search for pathfinding in video games. In Artificial Intelligence for Computer Games.
49. P. Butterworth, A. Otis, and J. Stein. 1991. The GemStone object database management system. Communications of the ACM 34, 10, 64--77.
50. S. Cabello. 2012. Many distances in planar graphs. Algorithmica 62, 1--2, 361--381.
51. S. Cabello, E. W. Chambers, and J. Erickson. 2012. Multiple-source shortest paths in embedded graphs. arXiv abs/1202.0314.
52. L. Cao, X. Zhao, H. Zheng, and B. Y. Zhao. 2011. Atlas: Approximating shortest paths in social graphs. Tech. rep. 2011-09, Department of Computer Science, University of California, Santa Barbara.
53. L. Chang, J. X. Yu, L. Qin, H. Cheng, and M. Qiao. 2012. The exact distance to destination in undirected world. VLDB Journal 21, 6, 869--888.
54. B. A. Chartres. 1967. Letter concerning Nicholson's paper. Computer Journal 10, 1, 118--119.
55. S. Chechik. 2013. Approximate distance oracle with constant query time. arXiv abs/1305.3314.
56. D. Z. Chen and J. Xu. 2000. Shortest path queries in planar graphs. In 32nd ACM Symposium on Theory of Computing (STOC). 469--478.
57. W. Chen, C. Sommer, S.-H. Teng, and Y. Wang. 2012. A compact routing scheme and approximate distance oracle for power-law graphs. ACM Transactions on Algorithms 9, 1, 4:1--26.
58. J. Cheng, Y. Ke, S. Chu, and C. Cheng. 2012. Efficient processing of distance queries in large graphs: a vertex cover approach. In ACM SIGMOD International Conference on Management of Data. 457--468.
59. J. Cheng and J. X. Yu. 2009. On-line exact shortest distance query processing. In 12th International Conference on Extending Database Technology (EDBT). 481--492.
60. J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. 2006. Fast computation of reachability labeling for large graphs. In 10th International Conference on Extending Database Technology (EDBT). 961--979.
61. J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. 2008. Fast computing reachability labelings for large graphs with high compression rate. In 11th International Conference on Extending Database Technology (EDBT). 193--204.
62. B. V. Cherkassky, A. V. Goldberg, and T. Radzik. 1996. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73, 129--174.
63. L. Chindelevitch, D. Ziemek, A. Enayetallah, R. Randhawa, B. Sidders, C. Brockel, and E. Huang. 2011. Causal reasoning on biological networks: Interpreting transcriptional changes. In 15th International Conference on Research in Computational Molecular Biology (RECOMB). 34--37.
64. F. R. K. Chung and L. Lu. 2002. The average distances in random graphs with given expected degrees. Internet Mathematics 99, 15879--15882.
65. A. Clauset, C. R. Shalizi, and M. E. J. Newman. 2009. Power-law distributions in empirical data. SIAM Review 51, 4, 661--703.
66. E. Cohen. 1998. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing 28, 1, 210--236.
67. E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing 32, 5, 1338--1355.
68. H. Cohen and E. Porat. 2010. On the hardness of distance oracle for sparse graph. arXiv abs/1006.1117.
69. M. Costa, M. Castro, A. I. T. Rowstron, and P. B. Key. 2004. PIC: Practical internet coordinates for distance estimation. In 24th International Conference on Distributed Computing Systems (ICDCS). 178--187.
70. A. Cvetkovski and M. Crovella. 2009. Hyperbolic embedding and routing for dynamic graphs. In 28th IEEE International Conference on Computer Communications (INFOCOM). 1647--1655.
71. F. Dabek, R. Cox, F. Kaashoek, and R. Morris. 2004. Vivaldi: a decentralized network coordinate system. In Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM). 15--26.
72. G. B. Dantzig. 1960. On the shortest route through a network. Management Science 6, 2, 187--190.
73. G. B. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press.
74. A. Das Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. 2010. A sketch-based distance oracle for web-scale graphs. In 3rd International Conference on Web Search and Web Data Mining (WSDM). 401--410.
75. D. Delling. 2009. Engineering and Augmenting Route Planning Algorithms. Ph.D. thesis, Universität Karlsruhe.
76. D. Delling, A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. 2013. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing 73, 7, 940--952.
77. D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. 2013a. Customizable Route Planning in Road Networks. Retrieved from http://research.microsoft.com/pubs/198358/crp_web_130724.pdf.
78. D. Delling, A. V. Goldberg, I. Razenshteyn, and R. F. F. Werneck. 2011. Graph partitioning with natural cuts. In 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). 1135--1146.
79. D. Delling, A. V. Goldberg, and R. F. Werneck. 2013b. Hub label compression. In 12th International Symposium on Experimental Algorithms (SEA). 18--29.
80. D. Delling, M. Holzer, K. Müller, F. Schulz, and D. Wagner. 2009. High-performance multi-level routing. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 73--92.
81. D. Delling, P. Sanders, D. Schultes, and D. Wagner. 2009a. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks - Design, Analysis, and Simulation. 117--139.
82. D. Delling, P. Sanders, D. Schultes, and D. Wagner. 2009b. Highway hierarchies star. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 141--174.
83. C. Demetrescu, A. V. Goldberg, and D. S. Johnson. 2008. Implementation challenge for shortest paths. In Encyclopedia of Algorithms.
84. E. Demir, C. Aykanat, and B. Barla Cambazoglu. 2008. Clustering spatial networks for aggregate query processing: A hypergraph approach. Information Systems 33, 1, 1--17.
85. N. Deo and C.-Y. Pang. 1984. Shortest path algorithms: Taxonomy and annotation. Networks 14, 257--323.
86. R. B. Dial, F. Glover, D. Karney, and D. Klingman. 1979. A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Networks 9, 215--248.
87. E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.
88. H. Djidjev. 1996. Efficient algorithms for shortest path problems on planar digraphs. In 22nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 151--165.
89. H. N. Djidjev. 1985. A linear algorithm for partitioning graphs of fixed genus. Serdica. Bulgariacae mathematicae publicationes 11, 4, 369--387.
90. H. N. Djidjev and C. Sommer. 2011. Approximate distance queries for weighted polyhedral surfaces. In 19th European Symposium on Algorithms (ESA). 579--590.
91. D. Dor, S. Halperin, and U. Zwick. 2000. All-pairs almost shortest paths. SIAM Journal on Computing 29, 5, 1740--1759.
92. J. E. Doran. 1967. An approach to automatic problem-solving. Machine Intelligence 1, 105--124.
93. S. E. Dreyfus. 1969. An appraisal of some shortest-path algorithms. Operations Research 17, 3, 395--412.
94. Z. Dvorak, D. Král, and R. Thomas. 2010. Deciding first-order properties for sparse graphs. In 51st IEEE Symposium on Foundations of Computer Science (FOCS). 133--142.
95. M. Enachescu, M. Wang, and A. Goel. 2008. Reducing maximum stretch in compact routing. In 27th IEEE International Conference on Computer Communications (INFOCOM). 336--340.
96. D. Eppstein. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3, 3.
97. D. Eppstein and M. T. Goodrich. 2008. Studying (non-planar) road networks through an algorithmic lens. In 16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS). 16.
98. P. Erdös. 1964. Extremal problems in graph theory. Theory of Graphs and its Applications, Proceedings of the Symposium Held in Smolenice, 29--36.
99. B. Eriksson, P. Barford, and R. D. Nowak. 2009. Estimating hop distance between arbitrary host pairs. In 28th IEEE International Conference on Computer Communications (INFOCOM). 801--809.
100. J. Fakcharoenphol and S. Rao. 2006. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences 72, 5, 868--889.
101. J. Fakcharoenphol and T. Saranurak. 2010. Improving stretch bound on the Patrascu--Roditty distance oracle. Preprint.
102. M. Faloutsos, P. Faloutsos, and C. Faloutsos. 1999. On power-law relationships of the Internet topology. In Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM). 251--262.
103. B. A. Farbey, A. H. Land, and J. D. Murchland. 1967. The cascade algorithm for finding all shortest distances in a directed graph. Management Science 14, 1, 19--28.
104. E. Feuerstein and A. Marchetti-Spaccamela. 1991. Dynamic algorithms for shortest paths in planar graphs. In 17th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 187--197.
105. R. W. Floyd. 1962. Algorithm 97: Shortest path. Communications of the ACM 5, 6, 345.
106. G. N. Frederickson. 1987. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing 16, 6, 1004--1022.
107. M. L. Fredman and R. E. Tarjan. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 3, 596--615.
108. L. Fu, D.-H. Sun, and L. R. Rilett. 2006. Heuristic shortest path algorithms for transportation applications: State of the art. Computers & Operations Research 33, 11, 3324--3343.
109. G. Gallo. 1980. Reoptimization procedures in shortest path problems. Rivista di Matematica per le Scienze Economiche e Sociali 3, 3--13.
110. C. Gavoille and D. Peleg. 2003. Compact and localized distributed data structures. Distributed Computing 16, 2--3, 111--120.
111. C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. 2004. Distance labeling in graphs. Journal of Algorithms 53, 1, 85--112.
112. C. Gavoille and C. Sommer. 2011. Sparse spanners vs. compact routing. In 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 225--234.
113. R. Geisberger, P. Sanders, D. Schultes, and D. Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In 7th International Workshop on Experimental Algorithms (WEA). 319--333.
114. R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3, 388--404.
115. H. L. Gelernter. 1963. Realization of a geometry theorem proving machine. Computers and Thought.
116. J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. 1984. A separator theorem for graphs of bounded genus. Journal of Algorithms 5, 3, 391--407.
117. D. E. Gilsinn and C. Witzgall. 1973. A performance comparison of labeling algorithms for calculating shortest path trees. Technical Note 772, National Institute of Standards and Technology.
118. A. Goldberg, H. Kaplan, and R. F. F. Werneck. 2006. Reach for A*: Efficient point-to-point shortest path algorithms. In 8th Workshop on Algorithm Engineering and Experiments (ALENEX). 129--143.
119. A. V. Goldberg. 2007. Point-to-point shortest path algorithms with preprocessing. In 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). 88--102.
120. A. V. Goldberg and C. Harrelson. 2005. Computing the shortest path: A* search meets graph theory. In 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 156--165.
121. A. V. Goldberg, H. Kaplan, and R. F. Werneck. 2009. Reach for A*: Shortest path algorithms with preprocessing. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 93--139.
122. A. V. Goldberg, H. Kaplan, and R. F. F. Werneck. 2007. Better landmarks within reach. In 6th International Workshop on Experimental Algorithms (WEA). 38--51.
123. A. V. Goldberg and R. F. F. Werneck. 2005. Computing point-to-point shortest paths from external memory. In 7th Workshop on Algorithm Engineering and Experiments (ALENEX). 26--40.
124. B. Golden. 1976. Shortest-path algorithms: A comparison. Operations Research 24, 6, 1164--1168.
125. R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. 1998. Proximity search in databases. In 24th International Conference on Very Large Data Bases (VLDB). 26--37.
126. A. Gubichev, S. J. Bedathur, S. Seufert, and G. Weikum. 2010. Fast and accurate estimation of shortest paths in large graphs. In 19th ACM Conference on Information and Knowledge Management (CIKM). 499--508.
127. J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. H. M. Smid. 2008. Approximate distance oracles for geometric spanners. ACM Transactions on Algorithms 4, 1.
128. S. Gupta, S. Kopparty, and C. Ravishankar. 2004. Roads, codes, and spatiotemporal queries. In 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 115--124.
129. R. Gutman. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In 6th Workshop on Algorithm Engineering and Experiments (ALENEX). 100--111.
130. S. Har-Peled and M. Mendel. 2006. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing 35, 5, 1148--1184.
131. P. E. Hart, N. J. Nilsson, and B. R. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Transactions of Systems Science and Cybernetics SSC-4, 2, 100--107.
132. M. R. Henzinger, P. N. Klein, S. Rao, and S. Subramanian. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1, 3--23.
133. J. Herzen, C. Westphal, and P. Thiran. 2011. Scalable routing easy as PIE: A practical isometric embedding protocol. In 19th IEEE International Conference on Network Protocols (ICNP). 49--58.
134. L. E. Hitchner. 1968. A comparative investigation of the computational efficiency of shortest path algorithms. Technical Report ORC 68-17, University of California at Berkeley.
135. A. J. Hoffman. 1963. On simple linear programming problems. In Symposia in Pure Mathematics VII. 317--327.
136. M. Holzer, F. Schulz, and D. Wagner. 2008. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics 13.
137. M. Holzer, F. Schulz, D. Wagner, and T. Willhalm. 2005. Combining speed-up techniques for shortest-path computations. ACM Journal of Experimental Algorithmics 10.
138. S. Honiden, M. E. Houle, C. Sommer, and M. Wolff. 2010. Approximate shortest path queries in graphs using Voronoi duals. Transactions on Computational Science 9, 28--53.
139. T. C. Hu. 1968. A decomposition algorithm for shortest paths in a network. Operations Research 16, 1, 91--102.
140. T. C. Hu. 1969. Integer Programming and Network Flows. Addison Wesley.
141. T. C. Hu and W. T. Torres. 1969. Shortcut in the decomposition algorithm for shortest paths in a network. IBM Journal of Research and Development 13, 4, 387--390.
142. T. Ikeda, M.-Y. Hsu, H. Imai, S. Nishimura, H. Shimoura, T. Hashimoto, K. Tenmoku, and K. Mitoh. 1994. A fast algorithm for finding better routes by AI search techniques. In Vehicle Navigation and Information Systems Conference. 291--296.
143. G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In 43rd ACM Symposium on Theory of Computing (STOC). 313--322.
144. R. Jin, Y. Xiang, N. Ruan, and D. Fuhry. 2009. 3-HOP: a high-compression indexing scheme for reachability query. In 35th SIGMOD International Conference on Management of Data (SIGMOD). 813--826.
145. R. Jin, Y. Xiang, N. Ruan, and H. Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In 34th ACM SIGMOD International Conference on Management of Data (SIGMOD). 595--608.
146. N. Jing, Y.-W. Huang, and E. A. Rundensteiner. 1996. Hierarchical optimization of optimal path finding for transportation applications. In 5th International Conference on Information and Knowledge Management (CIKM). 261--268.
147. N. Jing, Y.-W. Huang, and E. A. Rundensteiner. 1998. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Transactions on Knowledge and Data Engineering 10, 3, 409--432.
148. D. B. Johnson. 1977. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24, 1, 1--13.
149. S. Jung and S. Pramanik. 1996. HiTi graph model of topographical roadmaps in navigation systems. In 12th International Conference on Data Engineering (ICDE). 76--84.
150. S. Kannan, M. Naor, and S. Rudich. 1992. Implicit representation of graphs. SIAM Journal on Discrete Mathematics 5, 4, 596--603.
151. F. Karinthy. 1929. Lancszemek.
152. K. Kawarabayashi, P. N. Klein, and C. Sommer. 2011. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In 38th International Colloquium on Automata, Languages and Programming (ICALP). 135--146.
153. K. Kawarabayashi, C. Sommer, and M. Thorup. 2013. More compact oracles for approximate distances in undirected planar graphs. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). 550--563.
154. M. Kitamura and M. Yamazaki. 1965. On the connection of the two shortest route systems. In 8th Japanese Road Conference. 66--68.
155. V. L. Klee. 1964. A “string algorithm” for shortest path in directed networks. Operations Research 12, 3, 428--432.
156. P. N. Klein. 2002. Preprocessing an undirected planar network to enable fast approximate distance queries. In 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 820--827.
157. P. N. Klein. 2005. Multiple-source shortest paths in planar graphs. In 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 146--155.
158. P. N. Klein, S. Mozes, and C. Sommer. 2013. Structured recursive separator decompositions for planar graphs in linear time. In 45th ACM Symposium on Theory of Computing (STOC). 505--514.
159. P. N. Klein, S. Mozes, and O. Weimann. 2010. Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log²n)-time algorithm. ACM Transactions on Algorithms 6, 2.
160. P. N. Klein and S. Subramanian. 1998. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22, 3, 235--249.
161. J. M. Kleinberg. 2000. Navigation in a small world. Nature 406, 6798, 845.
162. J. M. Kleinberg, A. Slivkins, and T. Wexler. 2009. Triangulation and embedding using small sets of beacons. Journal of the ACM 56, 6.
163. E. Köhler, R. H. Möhring, and H. Schilling. 2005. Acceleration of shortest path and constrained shortest path computation. In 4th International Workshop on Experimental and Efficient Algorithms (WEA). 126--138.
164. L. Kowalik and M. Kurowski. 2006. Oracles for bounded-length shortest paths in planar graphs. ACM Transactions on Algorithms 2, 3, 335--363.
165. D. V. Krioukov, K. R. Fall, and X. Yang. 2004. Compact routing on Internet-like graphs. In 23rd IEEE International Conference on Computer Communications (INFOCOM).
166. R.-M. Kung, E. N. Hanson, Y. E. Ioannidis, T. K. Sellis, L. D. Shapiro, and M. Stonebraker. 1986. Heuristic search in database systems. In 1st International Workshop on Expert Database Systems. 537--548.
167. J. B. H. Kwa. 1989. BS*: An admissible bidirectional staged heuristic search algorithm. Artificial Intelligence 38, 1, 95--109.
168. A. H. Land and S. W. Stairs. 1967. The extension of the cascade algorithm to large graphs. Management Science 14, 1, 29--33.
169. U. Lauther. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität—von der Forschung zur praktischen Anwendung. Vol. 22. 219--230.
170. S. Lim, C. Sommer, E. Nikolova, and D. Rus. 2012. Practical route planning under delay uncertainty: Stochastic shortest path queries. In Robotics: Science and Systems VIII. 249--256.
171. R. J. Lipton, D. J. Rose, and R. E. Tarjan. 1979. Generalized nested dissection. SIAM Journal on Numerical Analysis 16, 346--358.
172. R. J. Lipton and R. E. Tarjan. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 2, 177--189.
173. J. Matousek. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics 93, 1, 333--344.
174. J. Maue, P. Sanders, and D. Matijevic. 2009. Goal-directed shortest-path queries using precomputed cluster distances. ACM Journal of Experimental Algorithmics 14, 3.2--3.27.
175. K. Mehlhorn and P. Sanders. 2008. Algorithms and data structures: the basic toolbox. Springer.
176. M. Mendel and A. Naor. 2007. Ramsey partitions and proximity data structures. Journal of the European Mathematical Society 9, 2, 253--275.
177. M. Mendel and C. Schwob. 2009. Fast C-K-R partitions of sparse graphs. Chicago Journal of Theoretical Computer Science, 1--18.
178. S. Milgram. 1967. The small world problem. Psychology Today 1, 61--67.
179. G. Mills. 1966. A decomposition algorithm for the shortest route problem. Operations Research 14, 279--286.
180. N. Milosavljevic. 2012. On optimal preprocessing for contraction hierarchies. In 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS). 33--38.
181. G. J. Minty. 1957. A comment on the shortest-route problem. Operations Research 5, 5, 724.
182. R. H. Möhring, H. Schilling, B. Schütz, D. Wagner, and T. Willhalm. 2006. Partitioning graphs to speedup Dijkstra's algorithm. ACM Journal of Experimental Algorithmics 11.
183. G. Monge. 1781. Mémoire sur la théorie des déblais et de remblais. Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, 666--704.
184. E. F. Moore. 1959. The shortest path through a maze. In Annals of the Computation Laboratory of Harvard University. Harvard University Press, 285--292.
185. S. Mozes and C. Sommer. 2012. Exact distance oracles for planar graphs. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). 209--222.
186. L. F. Muller and M. Zachariasen. 2007. Fast and compact oracles for approximate distances in planar graphs. In 15th European Symposium on Algorithms (ESA). 657--668.
187. J. D. Murchland. 1965. A new method for finding all elementary paths in a complete directed graph. Tech. rep. LBS-TNT-22, London Business School, Transport Network Theory Unit.
188. J. D. Murchland. 1967. The “once-through” method of finding all shortest distances in a graph from a single origin. Tech. rep. LBS-TNT-56, London Business School, Transport Network Theory Unit.
189. J. Nesetril and P. O. de Mendez. 2006. Linear time low tree-width partitions and algorithmic consequences. In 38th ACM Symposium on Theory of Computing (STOC). 391--400.
190. M. E. J. Newman. 2001. Scientific collaboration networks. II. shortest paths, weighted networks, and centrality. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics) 64.
191. T. S. E. Ng and H. Zhang. 2002. Predicting internet network distance with coordinates-based approaches. In 21st IEEE International Conference on Computer Communications (INFOCOM).
192. T. A. J. Nicholson. 1966. Finding the shortest route between two points in a network. The Computer Journal 9, 3, 275--280.
193. Y. Nussbaum. 2011. Improved distance queries in planar graphs. In 12th International Symposium on Algorithms and Data Structures (WADS). 642--653.
194. D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. 2003. Query processing in spatial network databases. In 29th International Conference on Very Large Data Bases (VLDB). 802--813.
195. F. Papadopoulos, D. V. Krioukov, M. Boguñá, and A. Vahdat. 2010. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In 29th IEEE International Conference on Computer Communications (INFOCOM). 2973--2981.
196. U. Pape. 1974. Implementation and efficiency of Moore-algorithms for the shortest route problem. Mathematical Programming 7, 1, 212--222.
197. M. Patrascu. 2011. Unifying the landscape of cell-probe lower bounds. SIAM Journal on Computing 40, 3, 827--847.
198. M. Patrascu and L. Roditty. 2010. Distance oracles beyond the Thorup-Zwick bound. In 51st IEEE Symposium on Foundations of Computer Science (FOCS). 815--823.
199. M. Patrascu, L. Roditty, and M. Thorup. 2012. A new infinity of distance oracles for sparse graphs. In 53rd IEEE Symposium on Foundations of Computer Science (FOCS). 738--747.
200. D. Peleg. 2000. Proximity-preserving labeling schemes. Journal of Graph Theory 33, 167--176.
201. I. S. Pohl. 1971. Bi-directional search. Machine Intelligence 6, 127--140.
202. M. Pollack and W. Wiebenson. 1960. Solutions of the shortest-route problem—a review. Operations Research 8, 2, 224--230.
203. E. Porat and L. Roditty. 2013. Preprocess, set, query! Algorithmica 67, 4, 516--528.
204. M. Potamias, F. Bonchi, C. Castillo, and A. Gionis. 2009. Fast shortest path distance estimation in large networks. In 18th ACM Conference on Information and Knowledge Management (CIKM). 867--876.
205. F. P. Preparata and M. I. Shamos. 1985. Computational geometry: an introduction.
206. M. Qiao, H. Cheng, L. Chang, and J. X. Yu. 2012. Approximate shortest distance computing: A query-dependent local landmark scheme. In 28th International Conference on Data Engineering (ICDE).
207. M. Qiao, H. Cheng, and J. X. Yu. 2011. Querying shortest path distance with bounded errors in large graphs. In 23rd International Conference on Scientific and Statistical Database Management (SSDBM). 255--273.
208. S. A. Rahman, P. Advani, R. Schunk, R. Schrader, and D. Schomburg. 2005. Metabolic pathway analysis web service (Pathway Hunter Tool at CUBIC). Bioinformatics 21, 7, 1189--1193.
209. B. Raney and K. Nagel. 2004. Iterative route planning for large-scale modular transportation simulations. Future Generation Computer Systems 20, 7, 1101--1118.
210. M. J. Rattigan, M. Maier, and D. Jensen. 2006. Using structure indices for efficient approximation of network properties. In 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 357--366.
211. M. J. Rattigan, M. Maier, and D. Jensen. 2007. Graph clustering with network structure indices. In 24th International Conference on Machine Learning (ICML). 783--790.
212. B. Riedhofer. 1997. Hierarchische Straßengraphen. M.S. thesis, Universität Stuttgart.
213. L. Roditty, M. Thorup, and U. Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In 32nd International Colloquium on Automata, Languages and Programming (ICALP). 261--272.
214. M. Roughan, W. Willinger, O. Maennel, D. Perouli, and R. Bush. 2011. 10 lessons from 10 years of measuring and modeling the Internet's autonomous systems. IEEE Journal on Selected Areas in Communications 29, 9, 1810--1821.
215. H. Samet, J. Sankaranarayanan, and H. Alborzi. 2008. Scalable network distance browsing in spatial databases. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 43--54.
216. A. L. Samuel. 1963. Some studies in machine learning using the game of checkers. Computers and Thought. 3, 211--229.
217. P. Sanders. 2009. Algorithm engineering—an attempt at a definition. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. 321--340.
218. P. Sanders and D. Schultes. 2005. Highway hierarchies hasten exact shortest path queries. In 13th European Symposium on Algorithms (ESA). 568--579.
219. P. Sanders and D. Schultes. 2006. Engineering highway hierarchies. In 14th European Symposium on Algorithms (ESA). 804--816.
220. P. Sanders, D. Schultes, and C. Vetter. 2008. Mobile route planning. In 16th European Symposium on Algorithms (ESA). 732--743.
221. J. Sankaranarayanan and H. Samet. 2009. Distance oracles for spatial networks. In 25th International Conference on Data Engineering (ICDE). 652--663.
222. J. Sankaranarayanan, H. Samet, and H. Alborzi. 2009. Path oracles for spatial networks. Proceedings of the VLDB Endowment 2, 1, 1210--1221.
223. J. L. Santos. 2009. Real-world applications of shortest path algorithms. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 1--19.
224. R. Schenkel, A. Theobald, and G. Weikum. 2004. HOPI: An efficient connection index for complex XML document collections. In 9th International Conference on Extending Database Technology (EDBT). 237--255.
225. R. Schenkel, A. Theobald, and G. Weikum. 2005. Efficient creation and incremental maintenance of the HOPI index for complex XML document collections. In 21st International Conference on Data Engineering (ICDE). 360--371.
226. J. P. Schmidt. 1998. All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM Journal on Computing 27, 4, 972--992.
227. D. Schultes. 2008. Route planning in road networks. Ph.D. thesis, Universität Karlsruhe.
228. D. Schultes and P. Sanders. 2007. Dynamic highway-node routing. In 6th International Workshop on Experimental Algorithms (WEA). 66--79.
229. F. Schulz, D. Wagner, and C. D. Zaroliagis. 2002. Using multi-level graphs for timetable information in railway systems. In 4th Workshop on Algorithm Engineering and Experiments (ALENEX). 43--59.
230. M. Schwartz and T. E. Stern. 1980. Routing techniques used in computer communication networks. IEEE Transactions on Communications 28, 4, 539--552.
231. R. Sedgewick and J. S. Vitter. 1986. Shortest paths in Euclidean graphs. Algorithmica 1, 1, 31--48. Announced at FOCS 1984.
232. S. Sen. 2009. Approximating shortest paths in graphs. In 3rd International Workshop on Algorithms and Computation (WALCOM). 32--43.
233. Y. Shavitt and T. Tankel. 2008. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Transactions on Networking 16, 25--36.
234. S. Shekhar, A. Fetterer, and B. Goyal. 1997. Materialization trade-offs in hierarchical shortest path algorithms. In 5th International Symposium on Advances in Spatial Databases (SSD). 94--111.
235. H. A. Smolleck. 1975. Application of fast sparse-matrix techniques and an energy estimation model for large transportation networks. Ph.D. thesis, University of Texas at Arlington.
236. H. A. Smolleck and M.-S. Chen. 1981. A new approach to near-optimal path assignment through electric-circuit modeling. Networks 11, 335--349.
237. C. Sommer. 2010. Approximate shortest path and distance queries in networks. Ph.D. thesis, The University of Tokyo.
238. C. Sommer, E. Verbin, and W. Yu. 2009. Distance oracles for sparse graphs. In 50th IEEE Symposium on Foundations of Computer Science (FOCS). 703--712.
239. B. Stout. 1999. Smart move: Intelligent path-finding. Retrieved from http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php.
240. M. Thorup. 2004. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM 51, 6, 993--1024.
241. M. Thorup and U. Zwick. 2001. Compact routing schemes. In ACM Symposium on Parallelism in Algorithms and Architectures. 1--10.
242. M. Thorup and U. Zwick. 2005. Approximate distance oracles. Journal of the ACM 52, 1, 1--24.
243. K. Tretyakov, A. Armas-Cervantes, L. García-Bañuelos, J. Vilo, and M. Dumas. 2011. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In 20th ACM Conference on Information and Knowledge Management (CIKM). 1785--1794.
244. P. Ungar. 1951. A theorem on planar graphs. Journal of the London Mathematical Societys 1--26, 4, 256--262.
245. D. van Vliet. 1978. Improved shortest path algorithms for transport networks. Transportation Research 12, 1, 7--20.
246. M. V. Vieira, B. M. Fonseca, R. Damazio, P. B. Golgher, D. de Castro Reis, and B. A. Ribeiro-Neto. 2007. Efficient search ranking in social networks. In 16th ACM Conference on Information and Knowledge Management (CIKM). 563--572.
247. D. Wagner and T. Willhalm. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In 11th European Symposium on Algorithms (ESA). 776--787.
248. D. Wagner and T. Willhalm. 2005. Drawing graphs to speed up shortest-path computations. In 7th Workshop on Algorithm Engineering and Experiments (ALENEX). 17--25.
249. D. Wagner and T. Willhalm. 2007. Speed-up techniques for shortest-path computations. In 24th Symposium on Theoretical Aspects of Computer Science (STACS). 23--36.
250. D. Wagner, T. Willhalm, and C. D. Zaroliagis. 2005. Geometric containers for efficient shortest-path computation. ACM Journal of Experimental Algorithmics 10.
251. S. Warshall. 1962. A theorem on boolean matrices. Journal of the ACM 9, 1, 11--12.
252. F. Wei. 2010. TEDI: efficient shortest path query answering on graphs. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 99--110.
253. C. Wulff-Nilsen. 2010. Algorithms for planar graphs and graphs in metric spaces. Ph.D. thesis, University of Copenhagen.
254. C. Wulff-Nilsen. 2012. Approximate distance oracles with improved preprocessing time. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). 202--208.
255. C. Wulff-Nilsen. 2013. Approximate distance oracles with improved query time. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). 539--549.
256. A. C.-C. Yao. 1981. Should tables be sorted? Journal of the ACM 28, 3, 615--628.
257. C. Zaroliagis. 2008. Engineering algorithms for large network applications. In Encyclopedia of Algorithms.
258. F. B. Zhan and C. E. Noon. 1998. Shortest path algorithms: An evaluation using real road networks. Transportation Science 32, 1, 65--73.
259. X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao. 2010. Orion: shortest path estimation for large social graphs. In 3rd Conference on Online Social Networks (WOSN). 9--9.
260. X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao. 2011. Efficient shortest paths on massive social graphs. In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). 77--86.
261. A. K. Ziliaskopoulos, D. Kotzinos, and H. S. Mahmassani. 1997. Design and implementation of parallel time-dependent least time path algorithms for intelligent transportation systems applications. Transportation Research Part C: Emerging Technologies 5, 2, 95--107.
262. U. Zwick. 2001. Exact and approximate distances in graphs—a survey. In 9th European Symposium on Algorithms (ESA). 33--48.

Index Terms

• Information systems

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Network flows

      • Paths and connectivity problems

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis