{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T10:41:09Z","timestamp":1774435269656,"version":"3.50.1"},"reference-count":38,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3485,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2004,1]]},"DOI":"10.1016\/s0304-3975(03)00402-x","type":"journal-article","created":{"date-parts":[[2003,8,8]],"date-time":"2003-08-08T07:31:32Z","timestamp":1060327892000},"page":"47-74","source":"Crossref","is-referenced-by-count":145,"title":["A new approach to all-pairs shortest paths on real-weighted graphs"],"prefix":"10.1016","volume":"312","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/S0304-3975(03)00402-X_BIB1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","article-title":"Faster algorithms for the shortest path problem","volume":"37","author":"Ahuja","year":"1990","journal-title":"J. ACM"},{"issue":"2, Part 1","key":"10.1016\/S0304-3975(03)00402-X_BIB2","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1006\/jcss.1997.1388","article-title":"On the exponent of the all pairs shortest path problem","volume":"54","author":"Alon","year":"1997","journal-title":"J. Comput. System Sci."},{"issue":"6","key":"10.1016\/S0304-3975(03)00402-X_BIB3","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1145\/355541.355562","article-title":"A minimum spanning tree algorithm with inverse-Ackermann type complexity","volume":"47","author":"Chazelle","year":"2000","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB4","series-title":"Introduction to Algorithms","author":"Cormen","year":"2001"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"10.1016\/S0304-3975(03)00402-X_BIB6","unstructured":"E.A. Dinic, Economical algorithms for finding shortest paths in a network, in: Y.S. Popkov, B.L. Shmulyian (Eds.), Transportation Modeling Systems, Institute for system studies, Moscow, 1978, pp. 36\u201344."},{"issue":"1","key":"10.1016\/S0304-3975(03)00402-X_BIB7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","article-title":"New bounds on the complexity of the shortest path problem","volume":"5","author":"Fredman","year":"1976","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB8","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithm","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB9","doi-asserted-by":"crossref","unstructured":"H.N. Gabow, A scaling algorithm for weighted matching on general graphs, in: Proc. 26th Annu. Symp. on Foundations of Computer Science (FOCS\u201985), 1985, pp. 90\u2013100.","DOI":"10.1109\/SFCS.1985.3"},{"issue":"5","key":"10.1016\/S0304-3975(03)00402-X_BIB10","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1137\/0218069","article-title":"Faster scaling algorithms for network problems","volume":"18","author":"Gabow","year":"1989","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/S0304-3975(03)00402-X_BIB11","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1997.2620","article-title":"All pairs shortest distances for graphs with small integer length edges","volume":"134","author":"Galil","year":"1997","journal-title":"Inform. and Comput."},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB12","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1137\/S0097539792231179","article-title":"Scaling algorithms for the shortest paths problem","volume":"24","author":"Goldberg","year":"1995","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB13","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/322203.322206","article-title":"Information bounds are weak in the shortest distance problem","volume":"27","author":"Graham","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB14","doi-asserted-by":"crossref","unstructured":"Y. Han, Improved fast integer sorting in linear space, in: Proc. 12th Annu. ACM\u2013SIAM Symp. on Discrete Algorithms (SODA), 2001, pp. 793\u2013796.","DOI":"10.1006\/inco.2001.3053"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB15","doi-asserted-by":"crossref","unstructured":"Y. Han, Deterministic sorting in O(nloglog n) time and linear space, in: 34th Annu. ACM Symp. on Theory of Computing, ACM Press, New York, 2002, pp. 602\u2013608.","DOI":"10.1145\/509907.509993"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB16","unstructured":"Y. Han, M. Thorup, Integer sorting in O(nloglog n) expected time and linear space, in: 43rd Annu. Symp. on Foundation of Computer Science, 2002, pp. 135\u2013144."},{"key":"10.1016\/S0304-3975(03)00402-X_BIB17","doi-asserted-by":"crossref","unstructured":"T. Hagerup, Improved shortest paths on the word RAM, in: Proc. 27th Internat. Colloq. on Automata, Languages, and Programming (ICALP\u201900), Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 61\u201372.","DOI":"10.1007\/3-540-45022-X_7"},{"issue":"1","key":"10.1016\/S0304-3975(03)00402-X_BIB18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321992.321993","article-title":"Efficient algorithms for shortest paths in sparse networks","volume":"24","author":"Johnson","year":"1977","journal-title":"J. ACM"},{"issue":"6","key":"10.1016\/S0304-3975(03)00402-X_BIB19","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1137\/0222071","article-title":"Finding the hidden path","volume":"22","author":"Karger","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(03)00402-X_BIB20","unstructured":"L.R. Kerr, The effect of algebraic structure on the computational complexity of matrix multiplication, Tech. Report TR70-75, Computer Science Department, Cornell University, June 1970."},{"issue":"1","key":"10.1016\/S0304-3975(03)00402-X_BIB21","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1006\/jagm.1998.0937","article-title":"Finding real-valued single-source shortest paths in o(n3) expected time","volume":"28","author":"Kolliopoulos","year":"1998","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB22","doi-asserted-by":"crossref","unstructured":"S. Pettie, On the comparison-addition complexity of all-pairs shortest paths, in: Proc. 13th Internat. Symp. on Algorithms and Computation (ISAAC\u201902), 2002, pp. 32\u201343.","DOI":"10.1007\/3-540-36136-7_4"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB23","doi-asserted-by":"crossref","unstructured":"S. Pettie, An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem, in: Proc. 43rd Annu. Symp. on Found. of Computer Science (FOCS\u201902), 2002, pp. 155\u2013163.","DOI":"10.1109\/SFCS.2002.1181892"},{"issue":"1","key":"10.1016\/S0304-3975(03)00402-X_BIB24","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/505241.505243","article-title":"An optimal minimum spanning tree algorithm","volume":"49","author":"Pettie","year":"2002","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB25","doi-asserted-by":"crossref","unstructured":"S. Pettie, V. Ramachandran, S. Sridhar, Experimental evaluation of a new shortest path algorithm, in: 4th Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, pp. 126\u2013142.","DOI":"10.1007\/3-540-45643-0_10"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB26","unstructured":"S. Pettie, V. Ramachandran, Computing shortest paths with comparisons and additions, in: Proc. 13th Annu. ACM\u2013SIAM Symp. on Discrete Algorithms (SODA\u201902), 2002, pp. 267\u2013276."},{"key":"10.1016\/S0304-3975(03)00402-X_BIB27","unstructured":"S. Pettie, V. Ramachandran, A shortest path algorithm for real-weighted undirected graphs, submitted. A preliminary version appeared in 13th ACM\u2013SIAM Symp. on Discrete Algorithms 2002, pp. 267\u2013276."},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB28","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jcss.1995.1078","article-title":"On the all-pairs-shortest-path problem in unweighted undirected graphs","volume":"51","author":"Seidel","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(03)00402-X_BIB29","doi-asserted-by":"crossref","unstructured":"A. Shoshan, U. Zwick, All pairs shortest paths in undirected graphs with integer weights, in: 40th Annu. Symp. on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Silver Spring, MD, 1999, pp. 605\u2013614.","DOI":"10.1109\/SFFCS.1999.814635"},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB30","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0204032","article-title":"On finding and updating spanning trees and shortest paths","volume":"4","author":"Spira","year":"1975","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/S0304-3975(03)00402-X_BIB31","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","article-title":"A class of algorithms which require nonlinear time to maintain disjoint sets","volume":"18","author":"Tarjan","year":"1979","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"10.1016\/S0304-3975(03)00402-X_BIB32","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","article-title":"A new upper bound on the complexity of the all pairs shortest path problem","volume":"43","author":"Takaoka","year":"1992","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB33","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1145\/316542.316548","article-title":"Undirected single-source shortest paths with positive integer weights in linear time","volume":"46","author":"Thorup","year":"1999","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB34","doi-asserted-by":"crossref","unstructured":"M. Thorup, Equivalence between priority queues and sorting, in: 43rd Annu. Symp. on Foundation of Computer Science, 2002, pp. 125\u2013134.","DOI":"10.1109\/SFCS.2002.1181889"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB35","doi-asserted-by":"crossref","unstructured":"M. Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, in: 35th Annu. ACM Symp. on Theory of Computers, 2003, pp. 149\u2013158.","DOI":"10.1145\/780564.780566"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB36","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","article-title":"Design and implementation of an efficient priority queue","volume":"10","author":"van Emde Boas","year":"1977","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(03)00402-X_BIB37","doi-asserted-by":"crossref","unstructured":"U. Zwick, Exact and approximate distances in graphs \u2014 a survey, in: Proc. 9th European Symp. on Algorithms (ESA), 2001, pp. 33\u201348.","DOI":"10.1007\/3-540-44676-1_3"},{"issue":"3","key":"10.1016\/S0304-3975(03)00402-X_BIB38","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/567112.567114","article-title":"All pairs shortest paths using bridging sets and rectangular matrix multiplication","volume":"49","author":"Zwick","year":"2002","journal-title":"J. ACM"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750300402X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750300402X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T05:49:49Z","timestamp":1585115389000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750300402X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S030439750300402X"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(03)00402-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}