{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T11:08:52Z","timestamp":1774436932438,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540695066","type":"print"},{"value":"9783540695073","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-69507-3_6","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T17:35:58Z","timestamp":1184607358000},"page":"88-102","source":"Crossref","is-referenced-by-count":33,"title":["Point-to-Point Shortest Path Algorithms with Preprocessing"],"prefix":"10.1007","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","first-page":"129","volume":"73","author":"B.V. Cherkassky","year":"1996","unstructured":"Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest Paths Algorithms: Theory and Experimental Evaluation. Math. Prog.\u00a073, 129\u2013174 (1996)","journal-title":"Math. Prog."},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Cowen, L.J., Wagner, C.G.: Compact Roundtrip Routing in Directed Networks. In: Proc. Symp. on Principles of Distributed Computation, pp. 51\u201359 (2000)","DOI":"10.1145\/343477.343516"},{"key":"6_CR3","volume-title":"Linear Programming and Extensions","author":"G.B. Dantzig","year":"1962","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton Univ. Press, Princeton (1962)"},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1287\/opre.27.1.161","volume":"27","author":"E.V. Denardo","year":"1979","unstructured":"Denardo, E.V., Fox, B.L.: Shortest-Route Methods: 1. Reaching, Pruning, and Buckets. Oper. Res.\u00a027, 161\u2013186 (1979)","journal-title":"Oper. Res."},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A Note on Two Problems in Connexion with Graphs. Numer. Math.\u00a01, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"6_CR6","first-page":"105","volume":"1","author":"J. Doran","year":"1967","unstructured":"Doran, J.: An Approach to Automatic Problem-Solving. Machine Intelligence\u00a01, 105\u2013127 (1967)","journal-title":"Machine Intelligence"},{"key":"6_CR7","unstructured":"Dreyfus, D.: An Appraisal of Some Shortest Path Algorithms. Technical Report RM-5433, Rand Corporation, Santa Monica, CA (1967)"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S.: Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time. In: Proc. 42nd\u00a0IEEE Annual Symposium on Foundations of Computer Science, pp. 232\u2013241 (2001)","DOI":"10.1109\/SFCS.2001.959897"},{"key":"6_CR9","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. J. Assoc. Comput. Mach.\u00a034, 596\u2013615 (1987)","journal-title":"J. Assoc. Comput. Mach."},{"key":"6_CR10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02288320","volume":"13","author":"G. Gallo","year":"1988","unstructured":"Gallo, G., Pallottino, S.: Shortest Paths Algorithms. Annals of Oper. Res.\u00a013, 3\u201379 (1988)","journal-title":"Annals of Oper. Res."},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/3-540-44676-1_19","volume-title":"Algorithms - ESA 2001","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: A Simple Shortest Path Algorithm with Linear Average Time. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 230\u2013241. Springer, Heidelberg (2001)"},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/3-540-45678-3_43","volume-title":"Algorithms and Computation","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: Shortest Path Algorithms: Engineering Aspects. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, p. 502. Springer, Heidelberg (2001)"},{"key":"6_CR13","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the Shortest Path: A* Search Meets Graph Theory. Technical Report MSR-TR-2004-24, Microsoft Research (2004)"},{"key":"6_CR14","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the Shortest Path: A* Search Meets Graph Theory. In: Proc. 16th\u00a0ACM-SIAM Symposium on Discrete Algorithms pp. 156\u2013165 (2005)"},{"key":"6_CR15","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.F.: Better Landmarks within Reach. In: The 9th\u00a0DIMACS Implementation Challenge: Shortest Paths (2006)"},{"key":"6_CR16","volume-title":"Proc. 7th\u00a0International Workshop on Algorithm Engineering and Experiments","author":"A.V. Goldberg","year":"2006","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.F.: Reach for A*: Efficient Point-to-Point Shortest Path Algorithms. In: Proc. 7th\u00a0International Workshop on Algorithm Engineering and Experiments, SIAM, Philadelphia (2006)"},{"key":"6_CR17","first-page":"292","volume-title":"Lecture Notes in Economics and Mathematical Systems","author":"A.V. Goldberg","year":"1997","unstructured":"Goldberg, A.V., Silverstein, C.: Implementations of Dijkstra\u2019s Algorithm Based on Multi-Level Buckets. In: Pardalos, P.M., Hearn, D.W. (eds.) Lecture Notes in Economics and Mathematical Systems, pp. 292\u2013327. Springer, Heidelberg (1997)"},{"key":"6_CR18","first-page":"26","volume-title":"Proc. 7th\u00a0International Workshop on Algorithm Engineering and Experiments","author":"A.V. Goldberg","year":"2005","unstructured":"Goldberg, A.V., Werneck, R.F.: Computing Point-to-Point Shortest Paths from External Memory. In: Proc. 7th\u00a0International Workshop on Algorithm Engineering and Experiments, pp. 26\u201340. SIAM, Philadelphia (2005)"},{"key":"6_CR19","unstructured":"Gutman, R.: Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Proc. 6th\u00a0International Workshop on Algorithm Engineering and Experiments, pp. 100\u2013111 (2004)"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on System Science and Cybernetics\u00a04(2) (1968)","DOI":"10.1109\/TSSC.1968.300136"},{"key":"6_CR21","volume-title":"Proc. Vehicle Navigation and Information Systems Conference","author":"T. Ikeda","year":"1994","unstructured":"Ikeda, T., Hsu, M.-Y., Imai, H., Nishimura, S., Shimoura, H., Hashimoto, T., Tenmoku, K., Mitoh, K.: A Fast Algorithm for Finding Better Routes by AI Search Techniques. In: Proc. Vehicle Navigation and Information Systems Conference, IEEE Computer Society Press, Los Alamitos (1994)"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1287\/opre.10.4.476","volume":"10","author":"R. Jacob","year":"1962","unstructured":"Jacob, R., Marathe, M.V., Nagel, K.: A Computational Study of Routing Algorithms for Realistic Transportation Networks. Oper. Res.\u00a010, 476\u2013499 (1962)","journal-title":"Oper. Res."},{"key":"6_CR23","unstructured":"Klein, P.: Preprocessing an Undirected Planar Network to Enable Fast Approximate Distance Queries. In: Proc. 13th\u00a0ACM-SIAM Symposium on Discrete Algorithms, pp. 820\u2013827 (2002)"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/11427186_13","volume-title":"Experimental and Efficient Algorithms","author":"E. K\u00f6hler","year":"2005","unstructured":"K\u00f6hler, E., M\u00f6hring, R.H., Schilling, H.: Acceleration of shortest path and constrained shortest path computation. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 126\u2013138. Springer, Heidelberg (2005)"},{"key":"6_CR25","unstructured":"Ford Jr., L.R.: Network Flow Theory. Technical Report P-932, The Rand Corporation (1956)"},{"key":"6_CR26","volume-title":"Flows in Networks","author":"L.R. Ford Jr.","year":"1962","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton Univ. Press, Princeton (1962)"},{"key":"6_CR27","unstructured":"Lauther, U.: An Extremely Fast, Exact Algorithm for Finding Shortest Paths in Static Networks with Geographical Background. In: IfGIprints 22, Institut fuer Geoinformatik, Universitaet Muenster, pp. 219\u2013230 (2004)"},{"key":"6_CR28","unstructured":"Meyer, U.: Single-Source Shortest Paths on Arbitrary Directed Graphs in Linear Average Time. In: Proc. 12th\u00a0ACM-SIAM Symposium on Discrete Algorithms, pp. 797\u2013806 (2001)"},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/11427186_18","volume-title":"Experimental and Efficient Algorithms","author":"R.H. M\u00f6hring","year":"2005","unstructured":"M\u00f6hring, R.H., Schilling, H., Sch\u00fctz, B., Wagner, D., Willhalm, T.: Partitioning Graphs to Speed up Dijkstra\u2019s Algorithm. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 189\u2013202. Springer, Heidelberg (2005)"},{"key":"6_CR30","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1093\/comjnl\/9.3.275","volume":"9","author":"T.A.J. Nicholson","year":"1966","unstructured":"Nicholson, T.A.J.: Finding the Shortest Route Between Two Points in a Network. Computer J.\u00a09, 275\u2013280 (1966)","journal-title":"Computer J."},{"key":"6_CR31","first-page":"124","volume-title":"Machine Intelligence","author":"I. Pohl","year":"1971","unstructured":"Pohl, I.: Bi-Directional Search. In: Machine Intelligence, vol.\u00a06, pp. 124\u2013140. Edinburgh Univ. Press, Edinburgh (1971)"},{"key":"6_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/11561071_51","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Sanders","year":"2005","unstructured":"Sanders, P., Schultes, D.: Highway Hierarchies Hasten Exact Shortest Path Queries. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 568\u2013579. Springer, Heidelberg (2005)"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1007\/11841036_71","volume-title":"Algorithms \u2013 ESA 2006","author":"P. Sanders","year":"2006","unstructured":"Sanders, P., Schultes, D.: Engineering highway hierarchies. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 804\u2013816. Springer, Heidelberg (2006)"},{"key":"6_CR34","unstructured":"Schultes, D.: Fast and Exact Shortest Path Queries Using Highway Hierarchies. Master\u2019s Thesis, Department of Computer Science, Universit\u00e4t des Saarlandes, Germany (2005)"},{"key":"6_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-45643-0_4","volume-title":"Algorithm Engineering and Experiments","author":"F. Schulz","year":"2002","unstructured":"Schulz, F., Wagner, D., Zaroliagis, C.D.: Using Multi-level Graphs for Timetable Information in Railway Systems. In: Mount, D.M., Stein, C. (eds.) ALENEX 2002. LNCS, vol.\u00a02409, pp. 43\u201359. Springer, Heidelberg (2002)"},{"key":"6_CR36","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01840435","volume":"1","author":"R. Sedgewick","year":"1986","unstructured":"Sedgewick, R., Vitter, J.S.: Shortest Paths in Euclidean Graphs. Algorithmica\u00a01, 31\u201348 (1986)","journal-title":"Algorithmica"},{"key":"6_CR37","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (1983)"},{"key":"6_CR38","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time. J. Assoc. Comput. Mach.\u00a046, 362\u2013394 (1999)","journal-title":"J. Assoc. Comput. Mach."},{"key":"6_CR39","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Compact Oracles for Reachability and Approximate Distances in Planar Digraphs. In: Proc. 42nd\u00a0IEEE Annual Symposium on Foundations of Computer Science, pp. 242\u2013251 (2001)","DOI":"10.1109\/SFCS.2001.959898"},{"key":"6_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1007\/978-3-540-39658-1_69","volume-title":"Algorithms - ESA 2003","author":"D. Wagner","year":"2003","unstructured":"Wagner, D., Willhalm, T.: Geometric speed-up techniques for finding shortest paths in large sparse graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 776\u2013787. Springer, Heidelberg (2003)"},{"key":"6_CR41","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/trsc.32.1.65","volume":"32","author":"F.B. Zhan","year":"1998","unstructured":"Zhan, F.B., Noon, C.E.: Shortest Path Algorithms: An Evaluation Using Real Road Networks. Transp. Sci.\u00a032, 65\u201373 (1998)","journal-title":"Transp. Sci."},{"key":"6_CR42","unstructured":"Zhan, F.B., Noon, C.E.: 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)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2007: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69507-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T04:01:34Z","timestamp":1556683294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69507-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695066","9783540695073"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69507-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}