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

Complexity and Approximate Algorithm of Shortest Paths in Dynamic Networks

作　　者：林澜[1] 闫春钢[1] 蒋昌俊[1] 周向东[2] 

机构地区：[1]同济大学电子与信息工程学院,上海200092 [2]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机学报》2007年第4期608-614,共7页Chinese Journal of Computers

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

摘　　要：有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.The shortest path problem of dynamic directed networks is significant in the disciplines of transportation and communication systems. In the classical models, the weight of each arc is invariant and usually given beforehand, but it may be varying in the practical problems. For instance, the running time of a car across a city block would be different according to the temporal traffic flow density. The shortest path problem in this context can be reduced to the Dynamic Single Source Shortest Path （DSSSP） problem. This paper first discusses the computational complexity and proves that the DSSSP problem is NP-hard. Then to aim to propose a new approximate algorithm for the DSSSP problem, the authors introduce the concept of the stability of the shortest path tree, and moreover, give the sufficient and necessary condition. The idea is as follows： first, a series of sectional linear functions are selected to approach the original nonlinear arc weight function. Then each corresponding linear time interval is partitioned into several stable subintervals, in which the dynamic shortest path tree maintains invariability. Finally, the holistic shortest path can be found by connecting the solutions in each stable subinterval. The effectiveness of the new algorithm is estimated by simulating experiments.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]