University of IsfahanTransactions on Combinatorics2251-86575320160901A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs23311260210.22108/toc.2016.12602ENMehdi KadivarAcademic member of Shahrekord UniversityJournal Article20150725We give an algorithm, called T$^{*}$, for finding the <em>k</em> 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<em> n</em> is the number of nodes and <em>m</em> 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.http://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf