文献类型：期刊文章

作　　者：谭国真[1] 高文[2]

机构地区：[1]大连理工大学计算机科学与工程系,大连116024 [2]中国科学院计算技术研究所

出　　处：《计算机学报》

基　　金：教育部科学技术重点项目 (990 2 5 );全国高等学校骨干教师基金项目;辽宁省自然科学基金项目 (9810 2 0 0 10 4)资助

年　　份：2002

卷　　号：25

期　　号：2

起止页码：165-172

语　　种：中文

收录情况：BDHX、BDHX2000、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、核心刊

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

关 键 词：网络优化 时间依赖  最小时间路径算法  计算机网络

分 类 号：TP393]