-
题名基于稳定分支的变权网络最优路径算法
被引量:10
- 1
-
-
作者
林澜
闫春钢
辛肖刚
蒋昌俊
-
机构
同济大学计算机科学与技术系
-
出处
《电子学报》
EI
CAS
CSCD
北大核心
2006年第7期1222-1225,共4页
-
基金
国家自然科学基金(No.60125205
90412013
+3 种基金
60473094
60534060)
国际重点合作项目(No.2005DFA10100)
上海市重大重点科技攻关项目(No.05DZ15007)
-
文摘
有向网络的最短路问题在交通、通讯系统的最优传输路径中有重要应用.在通常的模型中,每条弧的权是给定的.但在实际问题中,弧的权会发生变化,例如在交通拥堵时运行时间会变长.如果当权发生变化时,要重新调用最短路算法,则浪费计算时间.本文提出最短路稳定性的概念,给出了关于最短路长度稳定、最优解稳定与稳定分支的命题与理论证明,在此基础上给出一种新的变权网络最短路径算法,利用权发生变化前的信息,减少计算量,提高计算效率.通过模拟实验验证了该算法的有效性.
-
关键词
网络优化
最短路
变权
算法
稳定性
-
Keywords
network optimization
shortest path
varying weight
algorithm
stability
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-