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

On the K shortest path trees problem

Author

Listed:
  • Sedeño-Noda, Antonio
  • González-Martín, Carlos

Abstract

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,Cmax)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length Cmax, where O(f(n,m,Cmax)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:202:y:2010:i:3:p:628-635
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00484-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Namorado Climaco, Joao Carlos & Queiros Vieira Martins, Ernesto, 1982. "A bicriterion shortest path algorithm," European Journal of Operational Research, Elsevier, vol. 11(4), pages 399-404, December.
    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. Donald Goldfarb & Jianxiu Hao & Sheng-Roan Kai, 1990. "Efficient Shortest Path Simplex Algorithms," Operations Research, INFORMS, vol. 38(4), pages 624-628, August.
    4. 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.
    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. M. Cerf, 2013. "Multiple Space Debris Collecting Mission—Debris Selection and Trajectory Optimization," Journal of Optimization Theory and Applications, Springer, vol. 156(3), pages 761-796, March.

    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. 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.
    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.
    3. 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.
    4. Luigi Di Puglia Pugliese & Francesca Guerriero, 2013. "A Reference Point Approach for the Resource Constrained Shortest Path Problems," Transportation Science, INFORMS, vol. 47(2), pages 247-265, May.
    5. 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.
    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. 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.
    8. Bérubé, Jean-François & Gendreau, Michel & Potvin, Jean-Yves, 2009. "An exact [epsilon]-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits," European Journal of Operational Research, Elsevier, vol. 194(1), pages 39-50, April.
    9. 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.
    10. 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.
    11. Clímaco, João C.N. & Eugénia Captivo, M. & Pascoal, Marta M.B., 2010. "On the bicriterion - minimal cost/minimal label - spanning tree problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 199-205, July.
    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. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Qiang Tu & Han He & Xiaomin Lai & Chuan Jiang & Zhanji Zheng, 2024. "Identifying Critical Links in Degradable Road Networks Using a Traffic Demand-Based Indicator," Sustainability, MDPI, vol. 16(18), pages 1-20, September.
    20. Zhou, Bo & Eskandarian, Azim, 2006. "A Non-Deterministic Path Generation Algorithm for Traffic Networks," 47th Annual Transportation Research Forum, New York, New York, March 23-25, 2006 208047, Transportation Research Forum.

    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:202:y:2010:i:3:p:628-635. 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.