%0 Journal Article
%T A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs
%J Transactions on Combinatorics
%I University of Isfahan
%Z 2251-8657
%A Kadivar, Mehdi
%D 2016
%\ 09/01/2016
%V 5
%N 3
%P 23-31
%! A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs
%K $k$ shortest path problem
%K complexity of algorithms
%K ranking of paths
%R 10.22108/toc.2016.12602
%X 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.
%U https://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf