Premium
Finding the K th shortest path in a time‐schedule network
Author(s) -
Chen YenLiang,
Tang Kwei
Publication year - 2005
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20061
Subject(s) - shortest path problem , k shortest path routing , yen's algorithm , constrained shortest path first , schedule , node (physics) , shortest path faster algorithm , longest path problem , time complexity , floyd–warshall algorithm , average path length , computer science , path (computing) , euclidean shortest path , algorithm , mathematics , mathematical optimization , combinatorics , dijkstra's algorithm , theoretical computer science , computer network , graph , structural engineering , engineering , operating system
We consider the problem of finding the K th 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 K th shortest path. The proposed algorithm constructs a map structure at each node in the network, using which we can directly find the K th 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. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.