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

• 作者: 谭国真 高文
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 网络优化 最短路径 时间依赖的网络 算法
• 年，卷（期）: 2002,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 164-172
• 页数: 8页
• 分类号: TP301
• 字数: 9132字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.02.008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭国真	大连理工大学计算机科学与工程系	56	946	13.0	29.0