Cited By
View all- Udhayasekar SSrinivasan KKumar PChilukuri B(2024)Label-Setting Algorithm for Multi-Destination K Simple Shortest Paths Problem and ApplicationAlgorithms10.3390/a1708032517:8(325)Online publication date: 25-Jul-2024
Finding the k Shortest Simple Paths: Time and Space Trade-offs
Article No.: 1.11, Pages 1 - 23
Abstract
The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a source to a sink in a digraph. Yen (1971) proposed an algorithm with the best-known polynomial time complexity for this problem. Since then, the problem has been widely studied from an algorithm engineering perspective. The most noticeable proposals are the node-classification (NC) algorithm (Feng, 2014) and the sidetracks-based (SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant memory consumption.
We first show how to speed up the SB algorithm using dynamic updates of shortest path trees resulting in a faster algorithm (SB*) with the same memory consumption. We then propose the parsimonious SB (PSB) algorithm that significantly reduces the memory consumption of SB at the cost of a small increase of the running time. Furthermore, we propose the postponed node-classification (PNC) algorithm that combines the best of the NC and the SB algorithms. It offers a significant speed up compared to the SB algorithm while using the same amount of memory as the NC algorithm.
Our experimental results on complex networks show that all the considered algorithms have low memory consumption, and that the PSB algorithm is the fastest. On road networks, the relative performances of the algorithms depend on the number k of requested paths. Indeed, when the number k of requested paths is small (i.e., k ≤ 20 in our experiments), the SB* algorithm is the fastest among the considered algorithms, but it suffers from a large memory consumption and it offers very bad performances on some queries. When the number of requested paths is large (i.e., larger than 20 according to our experiments), the PNC algorithm is the fastest among the considered algorithms on road networks and it has a low memory footprint. The PNC algorithm is therefore a better choice on road networks.
References
[1]
Ali Al Zoobi, David Coudert, and Nicolas Nisse. 2020. Space and time trade-off for the k shortest simple paths problem. In Proceedings of the 18th International Symposium on Experimental Algorithms (SEA’20) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 160. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 18:1–18:13. DOI:
[2]
Ali Al Zoobi, David Coudert, and Nicolas Nisse. 2021. k Shortest Simple Paths (Version 2.0). Retrieved from https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths
[3]
M. Arita. 2000. Metabolic reconstruction using shortest paths. Simul. Pract. Theory 8, 1-2 (2000), 109–125. DOI:
[4]
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2016. Route planning in transportation networks. In Algorithm Engineering. Springer, 19–80.
[5]
M. Betz and H. Hild. 1995. Language models for a spelled letter recognizer. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Vol. 1. IEEE, 856–859. DOI:
[6]
Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D.-U. Hwang. 2006. Complex networks: Structure and dynamics. Phys. Rep. 424, 4-5 (2006), 175–308.
[7]
S. Clarke, A. Krikorian, and J. Rausen. 1963. Computing the n best loopless paths in a network. J. Soc. Indust. Appl. Math. 11, 4 (1963), 1096–1102. DOI:
[8]
Camil Demetrescu, Andrew V. Goldberg, and D. S. Johnson. 2006. 9th DIMACS Implementation Challenge—Shortest Paths. Retrieved from http://users.diag.uniroma1.it/challenge9/
[9]
D. Eppstein. 1998. Finding the k shortest paths. SIAM J. Comput. 28, 2 (1998), 652–673. DOI:
[10]
David Eppstein. 2016. Encyclopedia of Algorithms. Springer, New York, Chapter k-Best Enumeration, 1003–1006. DOI:
[11]
David Eppstein and Denis Kurz. 2017. K-best solutions of MSO problems on tree-decomposable graphs. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC’17), Vol. 89. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 16:1–16:13. DOI:
[12]
G. Feng. 2014. Finding k shortest simple paths in directed graphs: A node classification algorithm. Networks 64, 1 (2014), 6–17. DOI:
[13]
M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan. 1986. The pairing heap: A new form of self-adjusting heap. Algorithmica 1, 1 (1986), 111–129. DOI:
[14]
D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. 2000. Fully dynamic algorithms for maintaining shortest paths trees. J. Algor. 34, 2 (2000), 251–281. DOI:
[15]
Jun Gao, Huida Qiu, Xiao Jiang, Tengjiao Wang, and Dongqing Yang. 2010. Fast top-k simple shortest paths discovery in graphs. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 509–518.
[16]
Zvi Gotthilf and Moshe Lewenstein. 2009. Improved algorithms for the k simple shortest paths and the replacement paths problems. Inform. Process. Lett. 109, 7 (2009), 352–355.
[17]
Eleni Hadjiconstantinou and Nicos Christofides. 1999. An efficient implementation of an algorithm for finding k shortest simple paths. Networks 34, 2 (1999), 88–101. DOI:
[18]
Yijie Han and Tadao Takaoka. 2016. An \(O(n^3\log {\log {n}}/\log ^2{n})\) time algorithm for all pairs shortest paths. J. Discrete Algor. 38 (2016), 9–19.
[19]
J. Hershberger, M. Maxel, and S. Suri. 2007. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Trans. Algorithms 3, 4 (2007), 45. DOI:
[20]
W. Jin, S. Chen, and H. Jiang. 2013. Finding the k shortest paths in a time-schedule network with constraints on arcs. Comput. Oper. Res. 40, 12 (2013), 2975–2982. DOI:
[21]
David S. Johnson. 2002. A theoretician’s guide to the experimental analysis of algorithms. Data Struct., Near Neighbor Searches, Methodol. 59 (2002), 215–250. DOI:
[22]
N. Katoh, T. Ibaraki, and H. Mine. 1982. An efficient algorithm for k shortest simple paths. Networks 12, 4 (1982), 411–427. DOI:
[23]
D. Kurz. 2018. k-best Enumeration—Theory and Application. Theses. Technischen Universität Dortmund. DOI:
[24]
D. Kurz and P. Mutzel. 2016. A sidetrack-based algorithm for finding the k shortest simple paths in a directed graph. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC’16) (LIPIcs), Vol. 64. Schloss Dagstuhl, 49:1–49:13. DOI:
[25]
Eugene L. Lawler. 1972. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manage. Sci. 18, 7 (1972), 401–405.
[26]
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 1 (2007), 2–42. DOI:
[27]
Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http://snap.stanford.edu/data
[28]
Rose Oughtred, Chris Stark, Bobby-Joe Breitkreutz, Jennifer Rust, Lorrie Boucher, Christie Chang, Nadine Kolas, Lara O’Donnell, Genie Leung, Rochelle McAdam, et al. 2019. The BioGRID interaction database: 2019 update. Nucleic Acids Res. 47, D1 (2019), D529–D541.
[29]
Seth Pettie. 2004. A new approach to all-pairs shortest paths on real-weighted graphs. Theoret. Comput. Sci. 312, 1 (2004), 47–74.
[30]
Lukasz Salwinski, Christopher S. Miller, Adam J. Smith, Frank K. Pettit, James U. Bowie, and David Eisenberg. 2004. The database of interacting proteins: 2004 update. Nucleic Acids Res. 32, suppl_1 (2004), D449–D451.
[31]
T. Shibuya and H. Imai. 1997. New flexible approaches for multiple sequence alignment. J. Comput. Biol. 4, 3 (1997), 385–413. DOI:
[32]
Douglas R. Shier. 1979. On algorithms for finding the k shortest paths in a network. Networks 9, 3 (1979), 195–214.
[33]
The Cooperative Association for Internet Data Analysis (CAIDA). 2013. The CAIDA AS Relationships Dataset. Retrieved from http://www.caida.org/data/active/as-relationships/
[34]
Virginia Vassilevska Williams and Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS’10). IEEE, 645–654.
[35]
Feng Xie and David Levinson. 2007. Measuring the structure of road networks. Geograph. Anal. 39, 3 (2007), 336–356.
[36]
W. Xu, S. He, R. Song, and S. S. Chaudhry. 2012. Finding the k shortest paths in a schedule-based transit network. Comput. Oper. Res. 39, 8 (2012), 1812–1826. DOI:
[37]
J. Y. Yen. 1971. Finding the k shortest loopless paths in a network. Manage. Sci. 17, 11 (1971), 712–716. DOI:
Index Terms
- Finding the k Shortest Simple Paths: Time and Space Trade-offs
Recommendations
Finding the k shortest simple paths: A new algorithm and its implementation
We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed by Hershberger and Suri [2001], and can yield a factor ...
Finding non-dominated bicriteria shortest pairs of disjoint simple paths
In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an ...
Improved algorithms for the k simple shortest paths and the replacement paths problems
Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 December 2023
Online AM: 07 October 2023
Accepted: 20 September 2023
Revised: 26 July 2023
Received: 02 February 2021
Published in JEA Volume 28
Author Tag
Qualifiers
- Research-article
Funding Sources
- French government
- National Research Agency (ANR)
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 241Total Downloads
- Downloads (Last 12 months)222
- Downloads (Last 6 weeks)17
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View all- Udhayasekar SSrinivasan KKumar PChilukuri B(2024)Label-Setting Algorithm for Multi-Destination K Simple Shortest Paths Problem and ApplicationAlgorithms10.3390/a1708032517:8(325)Online publication date: 25-Jul-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format