No Access

Ranking One Million Simple Paths in Road Networks

Antonio Sedeño-Noda

Departamento de Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, C. P. 38271, San Cristóbal de La Laguna, Santa cruz de Tenerife, España

E-mail Address: asedeno@ull.edu.es

Search for more papers by this author

https://doi.org/10.1142/S0217595916500421Cited by:7 (Source: Crossref)

Abstract

In this paper, we address the problem of finding the $K$ best paths connecting a given pair of nodes in a directed graph with arbitrary lengths. We introduce an algorithm to determine the $K$ best paths in order of length when repeat nodes in the paths are allowed. We obtain an O $(m + n log n + K (n + log K))$ time and O $(K + m)$ space algorithm to implicitly determine the $K$ shortest paths in a directed graph with $n$ nodes and $m$ arcs. Empirical results where the algorithm was used to compute one hundred million paths in USA road networks are reported. A non-trivial modification of the previous algorithm is performed obtaining an O $(k_{1} (n m + log k_{1}))$ time method to compute paths without repeat nodes and to answer the next question: how many paths $k_{1}$ in practice are needed to identify $K$ simple paths using the previous algorithm? We find that the response is usually O $(K)$ based on an experiment computing one million paths in USA road networks. The determination of a theoretical tight bound on $k_{1}$ remains as an open problem.

Keywords:

References

Ahuja, R, T Magnanti and JB Orlin (1993). Network Flows. Prentice-Hall, inc. Google Scholar
Brander, A and MA Sinclair (1995). A comparative study of $K$ -shortest path algorithms. Proceedings of 11th UK Performance Engineering Workshop, pp. 370–379. Google Scholar
Carlyle, R and K Wood (2005). Near-shortest and K-shortest simple paths. Networks, 46(2), 98–109. Web of Science, Google Scholar
Cherkassky, BV, AV Goldberg and T Radzik (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programing, 73, 129–174. Web of Science, Google Scholar
Dijkstra, EW (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1, 269–271. Google Scholar
Eppstein, D (1999). Finding the $K$ shortest paths. SIAM Journal on Computing, 28, 653–674. Web of Science, Google Scholar
Gotthilf, Z and M Lewenstein (2009). Improved algorithms for the k shortest paths and the replacement paths problems. Information Processing Letters, 109, 352–355. Web of Science, Google Scholar
Hadjiconstantinou, E and N Chirstofides (1999). An efficient implementation of an algorithm for finding $K$ shortest simple paths. Networks, 34, 88–101. Web of Science, Google Scholar
Hershberger, J, M Maxel and S Suri (2007). Finding the $k$ Shortest Simple Paths: a new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 1290682. Web of Science, Google Scholar
Hoffman, W and R Pavley (1959). A method for the solution of the $N$ th best path problem. Journal of the ACM, 6, 506–514. Web of Science, Google Scholar
Jiménez, VM and A Marzal (1999). Computing the $K$ shortest paths: A new algorithm and an experimental comparison. Lecture Notes in Computer Science, 1668, 15–29. Google Scholar
Katoh, N, T Ibaraki and H Mine (1982). An efficient algorithm for $K$ shortest simple paths. Networks, 12, 411–427. Web of Science, Google Scholar
Lawler, EL (1972). A procedure for computing the $K$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401–405. Web of Science, Google Scholar
Martins, EQV, MMB Pascoal and J Santos (1999). Deviation algorithm for ranking shortest paths. International Journal of Foundations of Computer Science, 10(3), 247–263. Link, Google Scholar
Martins, EQV and MMB Pascoal (2003). A new implementation of Yen’s ranking loopless paths algorithm. 4OR — Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1, 121–134. Web of Science, Google Scholar
Pascoal, MMB (2006). Implementations and empirical comparison for K shortest loopless path algorithms. Online Proceedings of the Ninth DIMACS Implementation Challenge: The Shortest Path Problem, DIMACS, USA. Google Scholar
Pascoal, MMB and A Sedeño-Noda (2012). Enumerating K best paths in order of length in DAGs. European Journal of Operational Research, 221(2), 308–316. Web of Science, Google Scholar
Perko, A (1986). Implementation of algorithms for K shortest loopless paths. Networks, 16, 149–160. Web of Science, Google Scholar
Pollack, M (1961). The $k$ th best route through a network. Operations Research, 9, 578–580. Web of Science, Google Scholar
Roditty, L and U Zwick (2005). Replacement paths and $k$ simple shortest paths in unweighted directed graphs. ICALP 2005, ed. L. Caires et al., Lecture notes in Computer Science, Vol. 3580, Springer-Verlag, Berlin, pp. 249–260. Google Scholar
Sedeño-Noda, A and C González-Martín (2010). On the K shortest path trees problem. European Journal of Operational Research, 202, 628–635. Web of Science, Google Scholar
Sedeño-Noda, A (2012). An efficient time and space $K$ point-to-point shortest simple paths algorithm. Applied Mathematics and Computation, 218(20), 10244–10257. Web of Science, Google Scholar
Shier, D (1979). On algorithms for finding the k shortest paths in a network. Networks, 9, 195–214. Web of Science, Google Scholar
Skiscim, CC and BL Golden (1989). Solving k-shortest and constrained shortest path problems efficiently. Annals of Operations Research, 20, 249–282. Google Scholar
Yen, JY (1971). Finding the $K$ shortest loopless paths in a network. Management Science, 17, 712–716. Web of Science, Google Scholar
Yen, JY (1972). Another algorithm for finding the $K$ shortest loopless network paths. Proceedings of 41st Meetings of the Operations Research Society of America, Vol. 20. Google Scholar