Document Open Access Logo

A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph

Authors Denis Kurz, Petra Mutzel

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.49.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Denis Kurz
Petra Mutzel

Cite As Get BibTex

Denis Kurz and Petra Mutzel. A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.49

Abstract

We present an algorithm for the k shortest simple path problem on weighted directed graphs (kSSP) that is based on Eppstein’s algorithm for a similar problem in which paths are allowed to contain cycles. In contrast to most other algorithms for kSSP, ours is not based on Yen's algorithm [Networks, 1971] and does not solve replacement path problems. Its worst-case running time is on par with state-of-the-art algorithms for kSSP. Using our algorithm, one may find O(m) simple paths with a single shortest path tree computation and O(n+m) additional time per path in well-behaved cases, where n is the number of nodes and m is the number of edges. Our computational results show that on random graphs and large road networks, these well-behaved cases are quite common and our algorithm is faster than existing algorithms by an order of magnitude.

Subject Classification

Keywords
  • directed graph
  • k-best
  • shortest path
  • simple path
  • weighted graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aaron Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In SODA 2010, pages 742-755. SIAM, 2010. Google Scholar
  2. S. Clarke, A. Krikorian, and J. Rausen. Computing the N best loopless paths in a network. J. SIAM, 11(4):1096-1102, 1963. Google Scholar
  3. The Ninth DIMACS Implementation Challenge: 2005-2006. http://www.dis.uniroma1.it/challenge9/. Accessed: 2015-11-12.
  4. David Eppstein. Finding the k shortest paths. SIAM J. Comput., 28(2):652-673, 1998. Google Scholar
  5. David Eppstein. K-best enumeration. arXiv: 1412.5075v1 [cs.DS], 2014. Google Scholar
  6. Gang Feng. Finding k shortest simple paths in directed graphs: A node classification algorithm. Networks, 64(1):6-17, 2014. Google Scholar
  7. Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Inf. Comput., 104(2):197-214, 1993. Google Scholar
  8. Asaf Frieder and Liam Roditty. An experimental study on approximating k shortest simple paths. ACM J. Exp. Algorithmics, 19(1), 2014. Google Scholar
  9. Zvi Gotthilf and Moshe Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett., 109(7):352-355, 2009. Google Scholar
  10. John Hershberger, Matthew Maxel, and Subhash Suri. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Trans. Algorithms, 3(4), 2007. Google Scholar
  11. Naoki Katoh, Toshihide Ibaraki, and H. Mine. An efficient algorithm for K shortest simple paths. Networks, 12(4):411-427, 1982. Google Scholar
  12. Marta M. B. Pascoal. Implementations and empirical comparison of K shortest loopless path algorithms, 2006. 9th DIMACS Implementation Challenge Workshop: Shortest Paths. Google Scholar
  13. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47-74, 2004. Google Scholar
  14. Liam Roditty. On the k shortest simple paths problem in weighted directed graphs. SIAM J. Comput., 39(6):2363-2376, 2010. Google Scholar
  15. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms, 8(4):33, 2012. Google Scholar
  16. Sartaj Sahni. Data Structures, Algorithms, and Applications in C++. McGraw-Hill Pub. Co., 1st edition, 1999. Google Scholar
  17. Antonio Sedeño-Noda. An efficient time and space K point-to-point shortest simple paths algorithm. Appl. Math. and Comput., 218(20):10244-10257, 2012. Google Scholar
  18. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In FOCS 2010, pages 645-654, 2010. Google Scholar
  19. Jin Y. Yen. Finding the k shortest loopless paths in a network. Networks, 17(11):712-716, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact