{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:12:17Z","timestamp":1742937137009,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":18,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_377","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:20Z","timestamp":1461269000000},"page":"1996-1999","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Single-Source Shortest Paths"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"356_CR19353","volume-title":"Network flows: theory, algorithms, and applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnati TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs"},{"issue":"4","key":"356_CR19354","doi-asserted-by":"crossref","first-page":"431","DOI":"10.15807\/jorsj.43.431","volume":"43","author":"Y Asano","year":"2000","unstructured":"Asano Y, Imai H (2000) Practical efficiency of the linear-time algorithm for the single source shortest path problem. J Oper Res Soc Jpn 43(4):431\u2013447","journal-title":"J Oper Res Soc Jpn"},{"key":"356_CR19355","doi-asserted-by":"crossref","unstructured":"Bast H, Funke S, Matijevic D, Sanders P, Schultes D (2007) In transit to constant shortest-path queries in road networks. In: Proceedings 9th workshop on algorithm engineering and experiments (ALENEX), New Orleans","DOI":"10.1137\/1.9781611972870.5"},{"key":"356_CR19356","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT, Cambridge"},{"key":"356_CR19357","unstructured":"Demetrescu C, Goldberg AV, Johnson D (2006) 9th DIMACS implementation challenge-shortest paths. \n                  http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"issue":"3","key":"356_CR19358","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"AV Goldberg","year":"1995","unstructured":"Goldberg AV (1995) Scaling algorithms for the shortest paths problem. SIAM J Comput 24(3):494\u2013504","journal-title":"SIAM J Comput"},{"key":"356_CR19359","doi-asserted-by":"crossref","unstructured":"Goldberg AV (2001) Shortest path algorithms: engineering aspects. In: Proceedings of the 12th international symposium on algorithms and computation (ISAAC), Christchurch. LNCS, vol\u00a02223. Springer, Berlin, pp\u00a0502\u2013513","DOI":"10.1007\/3-540-45678-3_43"},{"key":"356_CR19360","doi-asserted-by":"crossref","unstructured":"Hagerup T (2000) Improved shortest paths on the word RAM. In: Proceedings of the 27th international colloquium on automata, languages, and programming (ICALP), Geneva. LNCS, vol\u00a01853. Springer, Berlin, pp\u00a061\u201372","DOI":"10.1007\/3-540-45022-X_7"},{"key":"356_CR19361","unstructured":"Han Y, Thorup M (2002) Integer sorting in \n                  \n                    \n                      O\n                      (\n                      n\n                      \n                        \n                          log\n                          log\n                          n\n                        \n                      \n                      )\n                    \n                  \n                  $$O(n\\sqrt{\\log \\log n})$$\n                 expected time and linear space. In: Proceedings of the 43rd symposium on foundations of computer science (FOCS), Vancouver, pp\u00a0135\u2013144"},{"key":"356_CR19362","doi-asserted-by":"crossref","unstructured":"Knopp S, Sanders P, Schultes D, Schulz F, Wagner D (2007) Computing many-to-many shortest paths using highway hierarchies. In: Proceedings of the 9th workshop on algorithm engineering and experiments (ALENEX), New Orleans","DOI":"10.1137\/1.9781611972870.4"},{"key":"356_CR19363","doi-asserted-by":"crossref","unstructured":"Pettie S (2002) On the comparison-addition complexity of all-pairs shortest paths. In: Proceedings of the 13th international symposium on algorithms and computation (ISAAC), Vancouver, pp\u00a032\u201343","DOI":"10.1007\/3-540-36136-7_4"},{"issue":"1","key":"356_CR19364","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 (2004) A new approach to all-pairs shortest paths on real-weighted graphs. Theor Comput Sci 312(1):47\u201374","journal-title":"Theor Comput Sci"},{"issue":"6","key":"356_CR19365","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S Pettie","year":"2005","unstructured":"Pettie S, Ramachandran V (2005) A shortest path algorithm for real-weighted undirected graphs. SIAM J Comput 34(6):1398\u20131431","journal-title":"SIAM J Comput"},{"key":"356_CR19366","doi-asserted-by":"crossref","unstructured":"Pettie S, Ramachandran V, Sridhar S (2002) Experimental evaluation of a new shortest path algorithm. In: Proceedings of the 4th workshop on algorithm engineering and experiments (ALENEX), San Francisco, pp\u00a0126\u2013142","DOI":"10.1007\/3-540-45643-0_10"},{"key":"356_CR19367","doi-asserted-by":"crossref","unstructured":"Sanders P, Schultes D (2006) Engineering highway hierarchies. In: Proceedings of the 14th European symposium on algorithms (ESA), Zurich, pp\u00a0804\u2013816","DOI":"10.1007\/11841036_71"},{"issue":"3","key":"356_CR19368","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M Thorup","year":"1999","unstructured":"Thorup M (1999) Undirected single-source shortest paths with positive integer weights in linear time. J ACM 46(3):362\u2013394","journal-title":"J ACM"},{"key":"356_CR19369","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1006\/jagm.2000.1080","volume":"35","author":"M Thorup","year":"2000","unstructured":"Thorup M (2000) Floats, integers, and single source shortest paths. J Algorithms 35:189\u2013201","journal-title":"J Algorithms"},{"key":"356_CR19370","unstructured":"Thorup M (2003) Quick and good facility location. In: Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms (SODA), Baltimore, pp\u00a0178\u2013185"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T14:47:40Z","timestamp":1553093260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_377","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}