{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:16:50Z","timestamp":1743131810984,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":19,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_377","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:30:58Z","timestamp":1214505058000},"page":"847-849","source":"Crossref","is-referenced-by-count":2,"title":["Single-Source Shortest Paths"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"377_CR1_377","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnati, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"issue":"4","key":"377_CR2_377","first-page":"431","volume":"43","author":"Y. Asano","year":"2000","unstructured":"Asano, Y., Imai, H.: Practical efficiency of the linear-time algorithm for the single source shortest path problem. J.\u00a0Oper. Res. Soc. Jpn. 43(4), 431\u2013447 (2000)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"377_CR3_377","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant shortest-path queries in road networks. In: Proceedings 9th Workshop on Algorithm Engineering and Experiments (ALENEX), 2007","DOI":"10.1137\/1.9781611972870.5"},{"key":"377_CR4_377","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"377_CR5_377","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.: 9th DIMACS Implementation Challege\u2014Shortest Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/ (2006)"},{"key":"377_CR6_377","unstructured":"Goldberg, A.V.: AVG Lab. http:\/\/www.avglab.com\/andrew\/"},{"issue":"3","key":"377_CR7_377","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"A.V. Goldberg","year":"1995","unstructured":"Goldberg, A.V.: Scaling algorithms for the shortest paths problem. SIAM J.\u00a0Comput. 24(3), 494\u2013504 (1995)","journal-title":"SIAM J. Comput."},{"key":"377_CR8_377","first-page":"502","volume-title":"Proc. 12th Int'l Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 2223","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: Shortest path algorithms: Engineering aspects. In: Proc.\u00a012th Int'l Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 2223, pp.\u00a0502\u2013513. Springer, Berlin (2001)"},{"key":"377_CR9_377","first-page":"61","volume-title":"Proc. 27th Int'l Colloq. on Automata, Languages, and Programming (ICALP). LNCS vol. 1853","author":"T. Hagerup","year":"2000","unstructured":"Hagerup, T.: Improved shortest paths on the word RAM. In: Proc. 27th Int'l Colloq. on Automata, Languages, and Programming (ICALP). LNCS vol. 1853, pp.\u00a061\u201372. Springer, Berlin (2000)"},{"key":"377_CR10_377","first-page":"135","volume-title":"Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS '02)","author":"Y. Han","year":"2002","unstructured":"Han, Y., Thorup, M.: Integer sorting in $$ { O(n\\sqrt{\\log\\log n}) } $$ expected time and linear space. In: Proc.\u00a043rd\u00a0Symp.\u00a0on Foundations of Computer Science (FOCS), 2002, pp.\u00a0135\u2013144"},{"key":"377_CR11_377","doi-asserted-by":"crossref","unstructured":"Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proceedings 9th Workshop on Algorithm Engineering and Experiments (ALENEX), 2007","DOI":"10.1137\/1.9781611972870.4"},{"key":"377_CR12_377","doi-asserted-by":"crossref","unstructured":"Pettie, S.: On the comparison\u2010addition complexity of all-pairs shortest paths. In: Proc. 13th Int'l Symp. on Algorithms and Computation (ISAAC), 2002, pp.\u00a032\u201343","DOI":"10.1007\/3-540-36136-7_4"},{"issue":"1","key":"377_CR13_377","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","volume":"312","author":"S. Pettie","year":"2004","unstructured":"Pettie, S.: A\u00a0new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci. 312(1), 47\u201374 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"377_CR14_377","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S. Pettie","year":"2005","unstructured":"Pettie, S., Ramachandran, V.: A\u00a0shortest path algorithm for real-weighted undirected graphs. SIAM J.\u00a0Comput. 34(6), 1398\u20131431 (2005)","journal-title":"SIAM J. Comput."},{"key":"377_CR15_377","doi-asserted-by":"crossref","unstructured":"Pettie, S., Ramachandran, V., Sridhar, S.: Experimental evaluation of a\u00a0new shortest path algorithm. In: Proc.\u00a04th Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, pp.\u00a0126\u2013142","DOI":"10.1007\/3-540-45643-0_10"},{"key":"377_CR16_377","first-page":"804","volume-title":"14th European Symposium on Algorithms. LNCS, vol. 4168","author":"P. Sanders","year":"2006","unstructured":"Sanders, P., Schultes, D.: Engineering Highway Hierarchies. In: Proc. 14th European Symposium on Algorithms (ESA), 2006, pp.\u00a0804\u2013816"},{"issue":"3","key":"377_CR17_377","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single\u2010source shortest paths with positive integer weights in linear time. J.\u00a0ACM 46(3), 362\u2013394 (1999)","journal-title":"J. ACM"},{"key":"377_CR18_377","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Floats, integers, and single source shortest paths. J.\u00a0Algorithms 35 (2000)","DOI":"10.1006\/jagm.2000.1080"},{"key":"377_CR19_377","unstructured":"Thorup, M.: Quick and good facility location. In: Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp.\u00a0178\u2013185"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T01:51:19Z","timestamp":1662169879000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_377"}},"subtitle":["1999; Thorup"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_377","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}