IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v221y2012i2p308-316.html
   My bibliography  Save this article

Enumerating K best paths in length order in DAGs

Author

Listed:
  • Pascoal, Marta M.B.
  • Sedeño-Noda, Antonio

Abstract

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k−1) trees (each of which contains a previous best path). An O(m+K(n+logK)) time and O(K+m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m+Kn) time using O(K+m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.

Suggested Citation

  • Pascoal, Marta M.B. & Sedeño-Noda, Antonio, 2012. "Enumerating K best paths in length order in DAGs," European Journal of Operational Research, Elsevier, vol. 221(2), pages 308-316.
    • Handle: RePEc:eee:ejores:v:221:y:2012:i:2:p:308-316
    DOI: 10.1016/j.ejor.2012.04.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712002779
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.04.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Stepanov, Alexander & Smith, James MacGregor, 2009. "Multi-objective evacuation routing in transportation networks," European Journal of Operational Research, Elsevier, vol. 198(2), pages 435-446, October.
    2. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    3. Eugene L. Lawler, 1972. "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem," Management Science, INFORMS, vol. 18(7), pages 401-405, March.
    4. Thomas H. Byers & Michael S. Waterman, 1984. "Technical Note—Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming," Operations Research, INFORMS, vol. 32(6), pages 1381-1384, December.
    5. Gomes, Teresa & Craveirinha, Jose, 2007. "Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1055-1064, September.
    6. Galand, Lucie & Perny, Patrice & Spanjaard, Olivier, 2010. "Choquet-based optimisation in multiobjective shortest path and spanning tree problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 303-315, July.
    7. Reinertsen, Harald & Vossen, Thomas W.M., 2010. "The one-dimensional cutting stock problem with due dates," European Journal of Operational Research, Elsevier, vol. 201(3), pages 701-711, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sedeño-Noda, Antonio & Alonso-Rodríguez, Sergio, 2015. "An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem," Applied Mathematics and Computation, Elsevier, vol. 265(C), pages 602-618.
    2. Guazzelli, Cauê Sauter & Cunha, Claudio B., 2018. "Exploring K-best solutions to enrich network design decision-making," Omega, Elsevier, vol. 78(C), pages 139-164.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fernández, Elena & Pozo, Miguel A. & Puerto, Justo & Scozzari, Andrea, 2017. "Ordered Weighted Average optimization in Multiobjective Spanning Tree Problem," European Journal of Operational Research, Elsevier, vol. 260(3), pages 886-903.
    2. Vedat Bayram & Hande Yaman, 2018. "Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach," Transportation Science, INFORMS, vol. 52(2), pages 416-436, March.
    3. Francesca Guerriero & Roberto Musmanno & Valerio Lacagnina & Antonio Pecorella, 2001. "A Class of Label-Correcting Methods for the K Shortest Paths Problem," Operations Research, INFORMS, vol. 49(3), pages 423-429, June.
    4. Guazzelli, Cauê Sauter & Cunha, Claudio B., 2018. "Exploring K-best solutions to enrich network design decision-making," Omega, Elsevier, vol. 78(C), pages 139-164.
    5. Sébastien Giguère & François Laviolette & Mario Marchand & Denise Tremblay & Sylvain Moineau & Xinxia Liang & Éric Biron & Jacques Corbeil, 2015. "Machine Learning Assisted Design of Highly Active Peptides for Drug Discovery," PLOS Computational Biology, Public Library of Science, vol. 11(4), pages 1-21, April.
    6. Antonio Sedeño-Noda, 2016. "Ranking One Million Simple Paths in Road Networks," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-20, October.
    7. Pushak, Yasha & Hare, Warren & Lucet, Yves, 2016. "Multiple-path selection for new highway alignments using discrete algorithms," European Journal of Operational Research, Elsevier, vol. 248(2), pages 415-427.
    8. Maren Martens & Martin Skutella, 2009. "Flows with unit path capacities and related packing and covering problems," Journal of Combinatorial Optimization, Springer, vol. 18(3), pages 272-293, October.
    9. Yunyue He & Zhong Liu & Jianmai Shi & Yishan Wang & Jiaming Zhang & Jinyuan Liu, 2015. "K-Shortest-Path-Based Evacuation Routing with Police Resource Allocation in City Transportation Networks," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-23, July.
    10. Belhoul, Lyes, 2014. "Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée," Economics Thesis from University Paris Dauphine, Paris Dauphine University, number 123456789/14672 edited by Vanderpooten, Daniel.
    11. Sedeño-Noda, Antonio & González-Martín, Carlos, 2010. "On the K shortest path trees problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 628-635, May.
    12. Sebastio, Stefano & Trivedi, Kishor S. & Wang, Dazhi & Yin, Xiaoyan, 2014. "Fast computation of bounds for two-terminal network reliability," European Journal of Operational Research, Elsevier, vol. 238(3), pages 810-823.
    13. Quang Minh Bui & Bernard Gendron & Margarida Carvalho, 2022. "A Catalog of Formulations for the Network Pricing Problem," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2658-2674, September.
    14. Daria Dzyabura & Srikanth Jagabathula, 2018. "Offline Assortment Optimization in the Presence of an Online Channel," Management Science, INFORMS, vol. 64(6), pages 2767-2786, June.
    15. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    16. Cuiyun Cheng & Xin Qian & Yuchao Zhang & Qingeng Wang & Jinbao Sheng, 2011. "Estimation of the evacuation clearance time based on dam-break simulation of the Huaxi dam in Southwestern China," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 57(2), pages 227-243, May.
    17. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    18. Doan, Xuan Vinh, 2022. "Distributionally robust optimization under endogenous uncertainty with an application in retrofitting planning," European Journal of Operational Research, Elsevier, vol. 300(1), pages 73-84.
    19. Hela Masri & Saoussen Krichen, 2018. "Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem," Annals of Operations Research, Springer, vol. 267(1), pages 353-377, August.
    20. Alessandra Griffa & Mathieu Mach & Julien Dedelley & Daniel Gutierrez-Barragan & Alessandro Gozzi & Gilles Allali & Joanes Grandjean & Dimitri Ville & Enrico Amico, 2023. "Evidence for increased parallel information transmission in human brain networks compared to macaques and male mice," Nature Communications, Nature, vol. 14(1), pages 1-15, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:221:y:2012:i:2:p:308-316. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.