{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T03:19:39Z","timestamp":1785813579087,"version":"3.56.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1996,5,1]],"date-time":"1996-05-01T00:00:00Z","timestamp":830908800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1996,5]]},"DOI":"10.1007\/bf02592101","type":"journal-article","created":{"date-parts":[[2007,3,29]],"date-time":"2007-03-29T15:55:47Z","timestamp":1175183747000},"page":"129-174","source":"Crossref","is-referenced-by-count":426,"title":["Shortest paths algorithms: Theory and experimental evaluation"],"prefix":"10.1007","volume":"73","author":[{"given":"Boris V.","family":"Cherkassky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz","family":"Radzik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"BF02592101_CR1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"R.K. Ahuja","year":"1990","unstructured":"R.K. Ahuja, K. Mehlhorn, J.B. Orlin and R.E. Tarjan, \u201cFaster algorithms for the shortest path problem\u201d,J. Assoc. Comput. Mach. 37 (2) (1990) 213\u2013223.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02592101_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R.E. Bellman","year":"1958","unstructured":"R.E. Bellman, \u201cOn a routing problem\u201d,Quart. Appl. Math. 16 (1958) 87\u201390.","journal-title":"Quart. Appl. Math."},{"key":"BF02592101_CR3","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas and E. Zijlstra, \u201cDesign and implementation of an efficient priority queue\u201d,Math. Syst. Theory 10 (1977) 99\u2013127.","journal-title":"Math. Syst. Theory"},{"key":"BF02592101_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson and R.L. Rivest,Introduction to Algorithms (MIT Press, Cambridge, MA, 1990)."},{"key":"BF02592101_CR5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1287\/opre.27.1.161","volume":"27","author":"E.V. Denardo","year":"1979","unstructured":"E.V. Denardo and B.L. Fox, \u201cShortest-route methods: 1. Reaching, pruning, and buckets\u201d,Operations Research 27 (1979) 161\u2013186.","journal-title":"Operations Research"},{"key":"BF02592101_CR6","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1145\/363269.363610","volume":"12","author":"R.B. Dial","year":"1969","unstructured":"R.B. Dial, \u201cAlgorithm 360: Shortest path forest with topological ordering\u201d,Comm. ACM 12 (1969) 632\u2013633.","journal-title":"Comm. ACM"},{"key":"BF02592101_CR7","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/net.3230090304","volume":"9","author":"R.B. Dial","year":"1979","unstructured":"R.B. Dial, F. Glover, D. Karney and D. Klingman, \u201cA computational analysis of alternative algorithms and labeling techniques for finding shortest path trees\u201d,Networks 9 (1979) 215\u2013248.","journal-title":"Networks"},{"key":"BF02592101_CR8","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"E.W. Dijkstra, \u201cA note on two problems in connection with graphs\u201d,Numer. Math. 1 (1959) 269\u2013271.","journal-title":"Numer. Math."},{"key":"BF02592101_CR9","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R.E. Erickson","year":"1979","unstructured":"R.E. Erickson, C.L. Monma and A.F. Veinott Jr., \u201cSend-and-split method for minimum-concave-cost network flows\u201d,Math. of Oper. Res. 12 (1979) 634\u2013664.","journal-title":"Math. of Oper. Res."},{"key":"BF02592101_CR10","volume-title":"Flows in Networks","author":"L.R. Ford Jr.","year":"1962","unstructured":"L.R. Ford Jr., and D.R. Fulkerson,Flows in Networks (Princeton Univ. Press, Princeton, NJ, 1962)"},{"key":"BF02592101_CR11","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"M.L. Fredman and R.E. Tarjan, \u201cFibonacci heaps and their uses in improved network optimization algorithms\u201d,J. Assoc. Comput. Mach. 34 (1987) 596\u2013615.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02592101_CR12","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"M.L. Fredman and D.E. Willard, \u201cTrans-dichotomous algorithms for minimum spanning trees and shortest paths\u201d,J. Comp. and Syst. Sci. 48 (1994) 533\u2013551.","journal-title":"J. Comp. and Syst. Sci."},{"key":"BF02592101_CR13","doi-asserted-by":"crossref","unstructured":"H.N. Gabow and R.E. Tarjan, \u201cFaster scaling algorithms for network problems\u201d,SIAM J. Comput. (1989) 1013\u20131036.","DOI":"10.1137\/0218069"},{"key":"BF02592101_CR14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02288320","volume":"13","author":"G. Gallo","year":"1988","unstructured":"G. Gallo and S. Pallottino, \u201cShortest paths algorithms\u201d,Annals of Oper. Res. 13 (1988) 3\u201379.","journal-title":"Annals of Oper. Res."},{"key":"BF02592101_CR15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230140103","volume":"14","author":"F. Glover","year":"1984","unstructured":"F. Glover, R. Glover and D. Klingman, \u201cComputational study of an improved shortest path algorithm\u201d,Networks 14 (1984) 25\u201337.","journal-title":"Networks"},{"key":"BF02592101_CR16","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/opre.33.1.65","volume":"33","author":"F. Glover","year":"1985","unstructured":"F. Glover, D. Klingman and N. Phillips, \u201cA new polynomially bounded shortest paths algorithm\u201d,Oper. Res. 33 (1985) 65\u201373.","journal-title":"Oper. Res."},{"key":"BF02592101_CR17","unstructured":"A.V. Goldberg, \u201cScaling algorithms for the shortest paths problem\u201d, in:Proceedings 4th ACM-SIAM Symposium on Discrete Algorithms (1993) 222\u2013231."},{"key":"BF02592101_CR18","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0893-9659(93)90022-F","volume":"6","author":"A.V. Goldberg","year":"1993","unstructured":"A.V. Goldberg and T. Radzik, \u201cA heuristic improvement of the Bellman-Ford algorithm\u201d,Applied Math. Let. 6 (1993) 3\u20136.","journal-title":"Applied Math. Let."},{"key":"BF02592101_CR19","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0305-0548(88)90052-4","volume":"15","author":"M.S. Hung","year":"1988","unstructured":"M.S. Hung and J.J. Divoky, \u201cA computational study of efficient shortest path algorithms\u201d,Comput. Oper. Res. 15 (1988) 567\u2013576.","journal-title":"Comput. Oper. Res."},{"key":"BF02592101_CR20","doi-asserted-by":"crossref","unstructured":"D.S. Johnson and C.C. McGeoch, eds.,Network Flows and Matching: First DIMACS Implementation Challenge (AMS, 1993).","DOI":"10.1090\/dimacs\/012"},{"key":"BF02592101_CR21","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1002\/net.3230110410","volume":"11","author":"A. Kershenbaum","year":"1981","unstructured":"A. Kershenbaum, \u201cA note on finding shortest paths trees\u201d,Networks 11 (1981) 399.","journal-title":"Networks"},{"key":"BF02592101_CR22","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt Reinhart, and Winston, New York 1976)."},{"key":"BF02592101_CR23","unstructured":"B.Ju. Levit and B.N. Livshits,Neleneinye Setevye Transportnye Zadachi (Transport, Moscow, 1972), in Russian."},{"key":"BF02592101_CR24","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1016\/0305-0548(91)90014-I","volume":"18","author":"J-F. Mondou","year":"1991","unstructured":"J-F. Mondou, T.G. Crainic and S. Nguyen, \u201cShortest path algorithms: A computational study with the C programming language\u201d,Comput. Oper. Res. 18 (1991) 767\u2013786.","journal-title":"Comput. Oper. Res."},{"key":"BF02592101_CR25","unstructured":"E.F. Moore, \u201cThe shortest path through a maze\u201d, in:Proceedings of the Int. Symp. on the Theory of Switching (Harvard University Press, 1959) 285\u2013292."},{"key":"BF02592101_CR26","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1002\/net.3230140206","volume":"14","author":"S. Pallottino","year":"1984","unstructured":"S. Pallottino, \u201cShortest-path methods: Complexity, interrelations and new propositions\u201d,Networks 14 (1984) 257\u2013267.","journal-title":"Networks"},{"key":"BF02592101_CR27","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/BF01585517","volume":"7","author":"U. Pape","year":"1974","unstructured":"U. Pape, \u201cImplementation and efficiency of Moore algorithms for the shortest root problem\u201d,Math. Prog. 7 (1974) 212\u2013222.","journal-title":"Math. Prog."},{"key":"BF02592101_CR28","doi-asserted-by":"crossref","first-page":"317","DOI":"10.6028\/jres.086.013","volume":"86","author":"D. Shier","year":"1981","unstructured":"D. Shier and C. Witzgall, \u201cProperties of labeling methods for determining shortest paths trees\u201d,J. Res. Natl. Bur. Stand. 86 (1981) 317\u2013330.","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"BF02592101_CR29","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"R.E. Tarjan,Data Structures and Network Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02592101.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02592101\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02592101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T23:37:52Z","timestamp":1558395472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02592101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,5]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,5]]}},"alternative-id":["BF02592101"],"URL":"https:\/\/doi.org\/10.1007\/bf02592101","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,5]]}}}