动态网络最短路问题的复杂性与近似算法

• 作者: 周向东 林澜 蒋昌俊 闫春钢
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 动态网络 最短路 算法 NP-困难 稳定性
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 608-614
• 页数: 7页
• 分类号: TP393
• 字数: 5683字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.04.013

摘要

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋昌俊	同济大学电子与信息工程学院	93	1492	18.0	36.0
2	周向东	复旦大学计算机与信息技术系	35	323	10.0	17.0
3	闫春钢	同济大学电子与信息工程学院	16	188	8.0	13.0
4	林澜	同济大学电子与信息工程学院	12	79	4.0	8.0