Finding the Kth shortest path in a time-schedule network

Finding the Kth shortest path in a time-schedule network

0.00 Avg rating0 Votes
Article ID: iaor20063621
Country: United States
Volume: 52
Issue: 1
Start Page Number: 93
End Page Number: 102
Publication Date: Feb 2005
Journal: Naval Research Logistics
Authors: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.