a new o(m+kn log 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 worstcase complexity is o(m+kn log d¯) in which n is the number of nodes and m is the number of arcs and 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‎.