基于稳定分支的变权网络最优路径算法

• 作者: 林澜 蒋昌俊 辛肖刚 闫春钢
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 网络优化 最短路 变权 算法 稳定性
• 年，卷（期）: 2006,（7）
• 所属期刊栏目: 学术论文
• 页码范围: 1222-1225
• 页数: 4页
• 分类号: TP301
• 字数: 4644字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2006.07.009

摘要

有向网络的最短路问题在交通、通讯系统的最优传输路径中有重要应用.在通常的模型中,每条弧的权是给定的.但在实际问题中,弧的权会发生变化,例如在交通拥堵时运行时间会变长.如果当权发生变化时,要重新调用最短路算法,则浪费计算时间.本文提出最短路稳定性的概念,给出了关于最短路长度稳定、最优解稳定与稳定分支的命题与理论证明,在此基础上给出一种新的变权网络最短路径算法,利用权发生变化前的信息,减少计算量,提高计算效率.通过模拟实验验证了该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋昌俊	同济大学计算机科学与技术系	93	1492	18.0	36.0
2	闫春钢	同济大学计算机科学与技术系	16	188	8.0	13.0
3	林澜	同济大学计算机科学与技术系	12	79	4.0	8.0
4	辛肖刚	同济大学计算机科学与技术系	1	21	1.0	1.0