A new O(m+knlogd) O(m+knlog⁡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鉹梁) 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ý ýmostefficient k shortest paths algorithms known so farý.