A new O(m + kn log d) algorithm to Find the k shortest paths in acyclic digraphs

Abstract

We give an algorithm, called T*, for finding the k shortest simplepaths connecting a certain pair of nodes, s and t, in a acyclic digraph.First the nodes of the graph are labeled according to the topologicalordering. Then for node i an ordered list of simple s − i paths iscreated. The length of the list is at most k and it is created by usingtournament trees. We prove the correctness of T* and show that itsworst-case complexity is O(m + kn log d) in which n is the number ofnodes and m is the number of arcs and d is the mean degree of thegraph. The algorithm has a space complexity of O(nk). An experimental evaluation of T*is presented which confirm the advantage of our algorithm comparedto the most efficient k shortest paths algorithms known so far.

Keywords

• k shortest path problem
• ranking path
• complexity of algorithms