时间依赖的网络中最小时间路径算法

被引：84

作者：

谭国真

高文

机构：

[1] 大连理工大学计算机科学与工程系

[2] 中国科学院计算技术研究所

来源：

计算机学报 | 2002年 / 02期

关键词：

网络优化; 最短路径; 时间依赖的网络; 算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

时间依赖的网络与传统网络模型相比更具有现实意义 ,具有广泛的应用领域 .交通网络和通信网络可以抽象为时间依赖的网络模型 .当模型中弧的长度是时间依赖的变量 ,最短路径问题的求解变得非常困难 ,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的 ,因此给出限制性条件使得传统最短路径算法是有效的 .该文从最短路径算法的理论基础入手 ,从理论上证明了传统最短路径算法 ,如 Dijkstra算法和标号设置算法 ,在时间依赖的网络上不能有效地求解最短路径问题 ;并且 ,在没有任何限制性条件下 ,给出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件和 SPTDN算法 ,从理论上证明了 SPTDN算法的正确性 .算法的实验结果是正确的 .最后给出了时间依赖的网络应用实例

引用

页码：165 / 172

页数：8

共 8 条

[1] 基于城市交通控制系统的动态车辆行驶路线选择的方法
杨兆升
李全喜
[J]. 公路交通科技, 1999, (01) : 3 - 5
[2] 车辆定位与导航系统[M]. 电子工业出版社 , (美)赵亦林著, 1999
[3] 网络最优化[M]. 高等教育出版社 , 刘家壮, 1991
[4] Floats, Integers, and Single Source Shortest Paths[J] . Mikkel Thorup.Journal of Algorithms . 2000 (2)
[5] Time–Work Tradeoffs of the Single-Source Shortest Paths Problem[J] . Hanmao Shi,Thomas H Spencer.Journal of Algorithms . 1999 (1)
[6] Minimum time paths in a network with mixed time constraints[J] . Y.L. Chen,Kwei Tang.Computers and Operations Research . 1998 (10)
[7] Shortest paths algorithms: Theory and experimental evaluation[J] . Boris V. Cherkassky,Andrew V. Goldberg,Tomasz Radzik.Mathematical Programming . 1996 (2)
[8] SHORTEST-PATH AND MINIMUM-DELAY ALGORITHMS IN NETWORKS WITH TIME-DEPENDENT EDGE-LENGTH
ORDA, A
ROM, R
[J]. JOURNAL OF THE ACM, 1990, 37 (03) : 607 - 625

← 1 →