Publications-Periodical Articles
Article View/Open
Publication Export
Google ScholarTM
NCCU Library
Citation Infomation
Related Publications in TAIR
| Title | Finding theKth shortest path in a time-schedule network |
| Creator | Tang, Kwei;Chen, Yen-Liang 唐揆 |
| Contributor | 企管系 |
| Key Words | 無 |
| Date | 2005 |
| Date Issued | 9-Mar-2015 16:18:11 (UTC+8) |
| Summary | 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. |
| Relation | Naval Research Logistics , 52(1), 93-102 |
| Type | article |
| DOI | http://dx.doi.org/10.1002/nav.20061 |
| dc.contributor | 企管系 | |
| dc.creator (作者) | Tang, Kwei;Chen, Yen-Liang | |
| dc.creator (作者) | 唐揆 | zh_TW |
| dc.date (日期) | 2005 | |
| dc.date.accessioned | 9-Mar-2015 16:18:11 (UTC+8) | - |
| dc.date.available | 9-Mar-2015 16:18:11 (UTC+8) | - |
| dc.date.issued (上傳時間) | 9-Mar-2015 16:18:11 (UTC+8) | - |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/73707 | - |
| dc.description.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. | |
| dc.format.extent | 125 bytes | - |
| dc.format.extent | 114 bytes | - |
| dc.format.mimetype | text/html | - |
| dc.format.mimetype | text/html | - |
| dc.relation (關聯) | Naval Research Logistics , 52(1), 93-102 | |
| dc.subject (關鍵詞) | 無 | |
| dc.title (題名) | Finding theKth shortest path in a time-schedule network | |
| dc.type (資料類型) | article | en |
| dc.identifier.doi (DOI) | 10.1002/nav.20061 | en_US |
| dc.doi.uri (DOI) | http://dx.doi.org/10.1002/nav.20061 | en_US |