On the K shortest path trees problem

Antonio Sedeño-Noda and Carlos González-Martín

European Journal of Operational Research, 2010, vol. 202, issue 3, 628-635

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 kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,Cmax)+Km) time and 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 Cmax, where 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.

Keywords: Network/graphs; K; shortest; path; trees; problem; Shortest; path; tree; problem; K; best; spanning; tree; K; best; solutions (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00484-6
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:202:y:2010:i:3:p:628-635

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().