{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:15:53Z","timestamp":1778300153541,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540664277","type":"print"},{"value":"9783540483182","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","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":[[1999]]},"DOI":"10.1007\/3-540-48318-7_4","type":"book-chapter","created":{"date-parts":[[2007,10,25]],"date-time":"2007-10-25T20:20:56Z","timestamp":1193343656000},"page":"15-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":102,"title":["Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison"],"prefix":"10.1007","author":[{"given":"V\u00edctor M.","family":"Jim\u00e9nez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9s","family":"Marzal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,27]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0377-2217(93)90095-5","volume":"69","author":"J.A. Azevedo","year":"1993","unstructured":"Azevedo, J.A., Costa, M.E.O.S., Madeira, J.J.E.R.S., Martins, E.Q.V.: An Algorithm for the Ranking of Shortest Paths. European J. Op. Res. 69 (1993) 97\u2013106","journal-title":"European J. Op. Res."},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/0377-2217(94)90162-7","volume":"73","author":"J.A. Azevedo","year":"1994","unstructured":"Azevedo, J.A., Madeira, J.J.E.R.S., Martins, E.Q.V., Pires, F.P.A.: A Computational Improvement for a Shortest Paths Ranking Algorithm. European J. Op. Res. 73 (1994) 188\u2013191","journal-title":"European J. Op. Res."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a Routing Problem. Quarterly Applied Math. 16 (1958) 87\u201390","journal-title":"Quarterly Applied Math."},{"key":"4_CR4","first-page":"582","volume":"8","author":"R. Bellman","year":"1960","unstructured":"Bellman, R., Kalaba, R.: On kth Best Policies. J. SIAM 8 (1960) 582\u2013588","journal-title":"J. SIAM"},{"key":"4_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge, MA (1990)"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"S.E. Dreyfus","year":"1969","unstructured":"Dreyfus, S.E.: An Appraisal of Some Shortest Path Algorithms. Op. Res. 17 (1969) 395\u2013412","journal-title":"Op. Res."},{"key":"4_CR7","unstructured":"Eppstein, D.: Finding the k Shortest Paths. In: Proc. 35th IEEE Symp. FOCS (1994) 154\u2013165"},{"issue":"2","key":"4_CR8","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Finding the k Shortest Paths. SIAM J. Computing 28(2) (1999) 652\u2013673","journal-title":"SIAM J. Computing"},{"issue":"1","key":"4_CR9","first-page":"66","volume":"11","author":"B.L. Fox","year":"1973","unstructured":"Fox, B.L.: Calculating kth Shortest Paths. INFOR-Canad. J. Op. Res. and Inform. Proces. 11(1) (1973) 66\u201370","journal-title":"INFOR-Canad. J. Op. Res. and Inform. Proces"},{"issue":"5","key":"4_CR10","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/opre.26.5.686","volume":"26","author":"B.L. Fox","year":"1978","unstructured":"Fox, B.L.: Data Structures and Computer Science Techniques in Operations Research. Op. Res. 26(5) (1978) 686\u2013717","journal-title":"Op. Res."},{"key":"4_CR11","unstructured":"Jim\u00e9nez, V.M., Marzal, A.: A New Algorithm for Finding the N-Best Sentence Hypotheses in Continuous Speech Recognition. In: Casacuberta, F., Sanfeliu, A. (eds.): Advances in Pattern Recognition and Applications. World Scientific (1994) 218\u2013228. Translated from Proc. V Symp. of Spanish AERFAI (1992) 180-187"},{"key":"4_CR12","unstructured":"Jim\u00e9nez, V.M., Marzal, A., Monn\u00e9, J.: A Comparison of Two Exact Algorithms for Finding the N-Best Sentence Hypotheses in Continuous Speech Recognition. In: Proc. 4th ESCA Conf. EUROSPEECH (1995) 1071\u20131074"},{"key":"4_CR13","unstructured":"Jim\u00e9nez, V.M., Marzal, A., Vidal, E.: Efficient Enumeration of Sentence Hypotheses in Connected Word Recognition. In: Proc. 3rd ESCA Conf. EUROSPEECH (1993) 2183\u20132186"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0377-2217(84)90269-8","volume":"18","author":"E. Q. V. Martins","year":"1984","unstructured":"Martins, E. Q. V.: An Algorithm for Ranking Paths that may Contain Cycles. European J. Op. Res. 18 (1984) 123\u2013130","journal-title":"European J. Op. Res."},{"key":"4_CR15","unstructured":"Martins, E.Q.V., Santos, J.L.E.: A New Shortest Paths Ranking Algorithm. Technical report, Univ. de Coimbra, \nhttp:\/\/www.mat.uc.pt\/~eqvm\n\n (1996)"},{"key":"4_CR16","volume-title":"C\u00e1lculo de las K Mejores Soluciones a Problemas de Programaci\u00f3n Din\u00e1mica","author":"A. Marzal","year":"1994","unstructured":"Marzal, A.: C\u00e1lculo de las K Mejores Soluciones a Problemas de Programaci\u00f3n Din\u00e1mica. PhD thesis (in Spanish), Univ. Polit\u00e9cnica de Valencia, Spain (1994)"},{"key":"4_CR17","unstructured":"Marzal, A., Vidal, E.: A N-best sentence hypotheses enumeration algorithm with duration constraints based on the two level algorithm. In Proc. of the Int. Conf. on Pattern Recognition (1992)"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/0377-2217(91)90093-B","volume":"53","author":"S.P. Miaou","year":"1991","unstructured":"Miaou, S.P., Chin, S.M.: Computing K-Shortest Paths for Nuclear Spent Fuel Highway Transportation. European J. Op. Res. 53 (1991) 64\u201380","journal-title":"European J. Op. Res."},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230060303","volume":"6","author":"D.R. Shier","year":"1976","unstructured":"Shier, D.R.: Iterative Methods for Determining the k Shortest Paths in a Network. Networks 6 (1976) 205\u2013229","journal-title":"Networks"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230090303","volume":"9","author":"D.R. Shier","year":"1979","unstructured":"Shier, D.R.: On Algorithms for Finding the k Shortest Paths in a Network. Networks 9 (1979) 195\u2013214","journal-title":"Networks"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1002\/net.3230170308","volume":"17","author":"C.C. Skicism","year":"1987","unstructured":"Skicism, C.C., Golden, B.L.: Computing k-Shortest Path Lengths in Euclidean Networks. Networks 17 (1987) 341\u2013352","journal-title":"Networks"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF02216932","volume":"20","author":"C.C. Skicism","year":"1989","unstructured":"Skicism, C.C., Golden, B.L.: Solving k-Shortest and Constrained Shortest Path Problems Efficiently. Annals of Op. Res. 20 (1989) 249\u2013282","journal-title":"Annals of Op. Res."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48318-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T09:04:34Z","timestamp":1587805474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48318-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664277","9783540483182"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-48318-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"27 July 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}