Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481148 | European Journal of Operational Research | 2010 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Antonio Sedeño-Noda, Carlos González-Martín,