On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the k th shortest path tree is adjacent to at least one of the previous (k-1)(k-1) shortest path trees. Consequently, we design an O(f(n,m,Cmax)+Km)O(f(n,m,Cmax)+Km) time and O(K+m)O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length CmaxCmax, where O(f(n,m,Cmax))O(f(n,m,Cmax)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.