Finding the Kth shortest path in a time-schedule network

Yen Liang Chen, Kwei Tang

研究成果: 雜誌貢獻期刊論文同行評審

7 引文 斯高帕斯(Scopus)


We consider the problem of finding the Kth shortest path for a time-schedule network, where each node in the network has a list of prespecified departure times, and departure from the node can take place only at one of these departure times. We develop a polynomial time algorithm independent of K for finding the Kth shortest path. The proposed algorithm constructs a map structure at each node in the network, using which we can directly find the Kth shortest path without having to enumerate the first K - 1 paths. Since the same map structure is used for different K values, it is not necessary to reconstruct the table for additional paths. Consequently, the algorithm is suitable for directly finding multiple shortest paths in the same network. Furthermore, the algorithm is modified slightly for enumerating the first K shortest paths and is shown to have the lowest possible time complexity under a condition that holds for most practical networks.

頁(從 - 到)93-102
期刊Naval Research Logistics
出版狀態已出版 - 2月 2005


深入研究「Finding the Kth shortest path in a time-schedule network」主題。共同形成了獨特的指紋。