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

摘要：

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

关键词：网络优化、最短路径、时间依赖的网络、算法

所属期刊栏目：25

分类号：TP301(计算技术、计算机技术)

资助基金：教育部科学技术基金99025;全国高等学校骨干教师资助计划;辽宁省自然科学基金

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：164-172