TY - JOUR
ID - 12602
TI - A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Kadivar, Mehdi
AD - Academic member of Shahrekord University
Y1 - 2016
PY - 2016
VL - 5
IS - 3
SP - 23
EP - 31
KW - $k$ shortest path problem
KW - complexity of algorithms
KW - ranking of paths
DO - 10.22108/toc.2016.12602
N2 - 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.
UR - https://toc.ui.ac.ir/article_12602.html
L1 - https://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf
ER -