时间依赖有向无环网最小时间路径算法

《时间依赖有向无环网最小时间路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CN43-1258／TPISSN1007—130X计算机工程与科学COMPUTERENGINEERING&SCIENCE2008年第30卷第11期V01．30。No．11，2008文章编号：1007-130X(2008)11—0042—04时间依赖有向无环网最小时间路径算法。AMinimum——TimePathAlgorithminTime—-DependentDirectedAcyclicNetworks余伟辉，陈闳中YUWei-hui，CHENHong-zt啪g(同济大学电子与信息工程学院．上海201804)(SchoolofElectronic

2、sandInformationEngineering-Ton舀iUniversity-Shanghai201804。China)”摘要：经典模型及算法可解决固定弧权条件下的最短路问题，然而实际应用中弧权往往是动态的，即弧权依赖时间变化。本文提出一种特殊最短路径算法，即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法，克服了扩散法的一些显著缺点．文中证明了该理论的正确性，最后列举了一个传统算法不能解决的实例，证明了该算法的正确性．Abstract：Shortestpathproblemslieattheheartofnetworkf

3、lows。whicharisefrequentlyinbothengineeringandscierl-tificapplications．Intheclassicalnetworkmodels，theweightofeachareisinvariantandusuallygivenbeforehand，butitmaybevaryinginthepracticalproblemswhicharetime-dependent．Thispaperproposesareusableminimtan-timepathalgorithmforthesolut

4、iontOaspecialtime-dependentnetwork．directedacyclienetwork．T}lisalgorithmobtainsreusabletreebytheuseoftheimprovedBreadth-FirstSearchinlimitedtime，andmakesthehashindexofthisreusabletreetOimprovethecom-plexityofreuse．Wecangettheshortestpathfromtheleavesofatree，whichcontainthetimes

5、pentontravelingfromthelOOttOthe1eaf．Thenthispaperprovesthecorrectnessofthetheory．Intheend．thispapercitesanexamplewhichc锄notbeeffectivelyresolvedbytheclassicalalgoNthmstOprovethecorrectnessofthetheory．关键词：最小时问路径；时间依赖；有向无环网；扩散法；算法Keywor【k：minimum-timepath；time-dependant；directeda

6、cyclicnetwork；flooding；algorithm中图分类号：TP301．3文献标识码：A1引言最短路问题(ShortestPathProblem)是网络流中的一个基本问题，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题。对于经典的最短路问题，网络的结构都是预先给定的，弧的权(长度或者费用)也不变。但是，在实际应用中，弧的权往往是变化的。例如，在交通模型中，道路拥堵时，车流的速度将会变慢。在这种情况下，提出了时间依赖网络(TimeDependentNet-

7、work，简称TDN)，网络中各弧的权重随着时间而发生变化，有些文献称其为动态网络。TDN网络的最短路问题比传统的最短路问题更具有现实意义，引起了许多研究者的兴趣。传统的静态网络算法不能直接移植到TDN网络上，众多研究者从多个方面对TDN算法展开了研究。Dreyfus[1]给出了改进的Dijkstra算法求解TDN网络的最小时间。Frigioni等【2]给出了一种动态修正的Diik—stra算法，将动态弧分成权重增加和权重减小的两组分别进行处理。这两种方法都是以改进原有的经典最短路算法来处理时间依赖网络。Kaufman和Smith[3]给出了Drea

8、dUS算法在TDN网络中是不正确的例子，但并没有从理论上给予严格的证明，而是建立严格的一致性条件来限制“病态