Communications - Scientific Letters of the University of Zilina 2009, 11(3):11-14 | DOI: 10.26552/com.C.2009.3.11-14

A Multi Label Algorithm for K Shortest Paths Problem

Stanislav Paluch1
1 Faculty of Management Science and Informatics, University of Zilina, Slovakia

The paper presents an algorithm for computing k shortest walks or k shortest paths in a directed graph G (V, A). The proposed algorithm can be applied for solving the k shortest paths problem in an undirected graph G (V, E), too, by transforming the graph G (V,E) to the digraph G(V, A) where the arc set A contains a couple of arcs (u,v), (v,u) for every edge {u,v} E.

Keywords: no keywords

Published: September 30, 2009  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Paluch, S. (2009). A Multi Label Algorithm for K Shortest Paths Problem. Communications - Scientific Letters of the University of Zilina, 11(3), 11-14. doi: 10.26552/com.C.2009.3.11-14
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. GOTTHILFA, Z., LEWENSTEIN, M.: Improved algorithms for the k simple shortest paths and the replacement paths problems, Information Processing Letters, Vol. 109, 7/2009, Pages 352-355 Go to original source...
    2. MARTINS, E., Q., W., PASCOAL, M., M., B., SANTOS, J., L., E.: A New Implementation of Yen's Ranking Looples Path Algorithm, Investigacao Operacional, 2000
    3. PLESNIK, J.: Graph Algorithms (in Slovak), VEDA Bratislava, 1983
    4. YEN, J., Y.: Finding k Shortest Loopless Paths in a Network, Managements Science, 17:712 760, 1971 Go to original source...
    5. YEN, J., Y.: Shortest Paths Network Problems, Mathematical Systems in Economics, Heft 18, Meisennheim am Glan, 1975.

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content