Kadivar, M. (2016). A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs. Transactions on Combinatorics, 5(3), 23-31. doi: 10.22108/toc.2016.12602

Mehdi Kadivar. "A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs". Transactions on Combinatorics, 5, 3, 2016, 23-31. doi: 10.22108/toc.2016.12602

Kadivar, M. (2016). 'A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs', Transactions on Combinatorics, 5(3), pp. 23-31. doi: 10.22108/toc.2016.12602

Kadivar, M. A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs. Transactions on Combinatorics, 2016; 5(3): 23-31. doi: 10.22108/toc.2016.12602

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

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.

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.