{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T15:32:50Z","timestamp":1762270370490},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1999,9]]},"abstract":"<jats:p> The shortest path problem is a classical network problem that has been extensively studied. The problem of determining not only the shortest path, but also listing the K shortest paths (for a given integer K&gt;1) is also a classical one but has not been studied so intensively, despite its obvious practical interest. Two different types of problems are usually considered: the unconstrained and the constrained K shortest paths problem. While in the former no restriction in considered in the definition of a path, in the constrained K shortest paths problem all the paths have to satisfy some condition \u2013 for example, to be loopless. <\/jats:p><jats:p> In this paper new algorithms are proposed for the uncontrained problem, which compute a super set of the K shortest paths. It is also shown that ranking loopless paths does not hold in general the Optimality Principle and how the proposed algorithms for the unconstrained problem can be adapted for ranking loopless paths. <\/jats:p>","DOI":"10.1142\/s0129054199000186","type":"journal-article","created":{"date-parts":[[2003,1,22]],"date-time":"2003-01-22T07:24:14Z","timestamp":1043220254000},"page":"247-261","source":"Crossref","is-referenced-by-count":114,"title":["DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS"],"prefix":"10.1142","volume":"10","author":[{"given":"ERNESTO","family":"DE QUEIR\u00d3S VIEIRA MARTINS","sequence":"first","affiliation":[{"name":"Centro de Inform\u00e1tica e Sistemas da Universidade de Coimbra, Departamento de Matem\u00e1tica, Universidade de Coimbra, Apartado 3008, 3000 Coimbra, Portugal"}]},{"given":"MARTA MARGARIDA BRAZ","family":"PASCOAL","sequence":"additional","affiliation":[{"name":"Centro de Inform\u00e1tica e Sistemas da Universidade de Coimbra, Departamento de Matem\u00e1tica, Universidade de Coimbra, Apartado 3008, 3000 Coimbra, Portugal"}]},{"given":"JOS\u00c9 LUIS ESTEVES DOS","family":"SANTOS","sequence":"additional","affiliation":[{"name":"Centro de Inform\u00e1tica e Sistemas da Universidade de Coimbra, Departamento de Matem\u00e1tica, Universidade de Coimbra, Apartado 3008, 3000 Coimbra, Portugal"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90095-5"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90162-7"},{"key":"p_4","first-page":"255","author":"Climaco J.C.N.","year":"1981","journal-title":"Konigstein"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(82)90205-3"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.1.161"},{"key":"p_7","first-page":"275","volume":"9","author":"Deo N.","year":"1979","journal-title":"Networks"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090304"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121087"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1145\/320998.321004"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120406"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90269-8"},{"key":"p_22","first-page":"139","volume":"78","author":"Shier D.","year":"1974","journal-title":"Journal of Research of the NBS"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230060303"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090303"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040204"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054199000186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:26:34Z","timestamp":1565137594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054199000186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,9]]},"references-count":20,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[1999,9]]}},"alternative-id":["10.1142\/S0129054199000186"],"URL":"https:\/\/doi.org\/10.1142\/s0129054199000186","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,9]]}}}