@article {
author = {Kadivar, Mehdi},
title = {A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs},
journal = {Transactions on Combinatorics},
volume = {5},
number = {3},
pages = {23-31},
year = {2016},
publisher = {University of Isfahan},
issn = {2251-8657},
eissn = {2251-8665},
doi = {10.22108/toc.2016.12602},
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 = {$k$ shortest path problem,complexity of algorithms,ranking of paths},
url = {https://toc.ui.ac.ir/article_12602.html},
eprint = {https://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf}
}