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‎.

Keywords:

k shortest path problem‎ , ‎complexity of algorithms‎ , ‎ranking of paths