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

作     者：林澜 闫春钢 蒋昌俊 周向东 LIN Lan;YAN Chun-Gang;JIANG Chang-Jun;ZHOU Xiang-Dong

作者机构：同济大学电子与信息工程学院上海200092 复旦大学计算机与信息技术系上海200433 

基　　金：国家自然科学基金(60534060 60473094 90412013) 国际重点合作项目基金(2005DFA10100) 上海市科委科技攻关项目基金(05DZ15004)资助 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2007年第30卷第4期

页      码：608-614页

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

主 题 词：动态网络 最短路 算法 NP-困难 稳定性 

学科分类：0810[工学-土木类] 12[管理学] 1201[管理学-管理科学与工程类] 0808[工学-自动化类] 0839[0839] 08[工学] 0835[0835] 0811[工学-水利类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3321/j.issn:0254-4164.2007.04.013

馆 藏 号：203150083...