Finding the Kth shortest path in a time-schedule network

Yen Liang Chen, Kwei Tang

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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.

Original languageEnglish
Pages (from-to)93-102
Number of pages10
JournalNaval Research Logistics
Issue number1
StatePublished - Feb 2005


Dive into the research topics of 'Finding the Kth shortest path in a time-schedule network'. Together they form a unique fingerprint.

Cite this