A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs

Document Type: Research Paper

Author

Abstract

‎We give an algorithm‎, ‎called T$^{*}$‎, ‎for finding the k shortest simple paths connecting a certain‎ ‎pair of nodes‎, ‎$s$ and $t$‎, ‎in a acyclic digraph‎. ‎First the nodes of the graph are labeled according to the topological ordering‎. ‎Then for node $i$ an ordered list of simple $s-i$ paths is created‎. ‎The length of the list is at most $k$ and it is created by using tournament trees‎. ‎We prove the correctness of T$^{*}$ and show that its worst-case complexity is $O(m+k n \log \overline{d})$ in which n is the number of nodes and m is the number of arcs and $\overline{d}$ is the mean degree of the graph‎. ‎The algorithm has a space complexity of $O(kn)$ which entails an important improvement in space complexity‎. ‎An experimental evaluation of T$^{*}$ is presented which confirms the advantage of our algorithm compared to the‎ ‎most efficient $k$ shortest paths algorithms known so far‎.

Keywords

Main Subjects

References

1] H. Aljazzar and S. Leue, $‎K^{*}$: a heuristic search algorithm for finding the k shortest paths, Artificial Intelligence, 175 no. 18 (2011) 2129–2154.

[2] J. A. Azevedo, M. E. O. Santos Costa, J. J. E. R. Silvestre Madeira and E. Q. V. Martins, An algorithm for the
ranking of shortest paths, European J. Oper. Res., 69 (1993) 97–106.

[3] C. Caliskan, A computational study of the capacity scaling algorithm for the maximum flow problem, Comput. Oper. Res., 39 no. 11 (2012) 2742–2747.

[4] Y. L. Chen, Finding thekquickest simple paths in a network, Information Processing Letters, 50 (1994) 89–92.

[5] D. Eppstein, Finding the ‎$‎K‎$ shortest paths, SIAM J. Comput., 28 (1999) 652–673.

[6] G. Feng, Finding ‎$‎K‎$ Shortest Simple Paths in Directed Graphs: A Node Classification Algorithm, Networks, 64
(2014) 6–17.

[7] G. N. Frederickson, An optimal algorithm for selection in a min-heap, Inform. and Comput., 104 (1993) 197–214.

[8] G. N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and $k$ smallest spanning trees, in: 32nd Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991 632–641.

[9] B. L. Fox, k-th shortest paths and applications to the probabilistic networks, ORSA/TIMS Joint National Mtg., 23 (1975) p. B263.

[10] Z. Gotthilf and M. Lewenstein, Improved algorithms for the $k$ simple shortest paths and the replacement paths problems, Inform. Process. Lett., 109 (2009) 352–355.

[11] W. Hoffman and R. Pavley, A method for the solution of the $N$ th best path problem, J. Assoc. Comput. Mach., 6 (1959) 506–514.

[12] V. M. Jimenez and A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop on Experimental and Efficient Algorithms, in: Lecture Notes in Computer Science, Springe, 2003 179–190.

[13] N. Katoh, T. Ibaraki and H. Mine, An efficient algorithm for $k$ shortest simple paths, Networks, 12 (1982) 411–427.

[14] S. P. Miaou and S. M. Chin, Computing ‎$‎K‎$-shortest path for nuclear spent fuel highway transportation, Eur. J. Operational Research, 53 (1991) 64–80.

[15] J. W. Suurballe, Disjoint paths in a network, Networks, 4 (1974) 125–145.

[16] J. Y. Yen, Finding the ‎$‎K‎$ shortest loopless paths in a network, Management Sci., 17 (1971) 712–716.