On the K shortest path trees problem |
| |
Authors: | Antonio Sedeo-Noda Carlos Gonzlez-Martín |
| |
Institution: | aUniversidad de La Laguna (DEIOC), 38271 La Laguna, Tenerife, Spain |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |
|