交通网络最短路径标号算法的实现与效率分析.pdf

《交通网络最短路径标号算法的实现与效率分析.pdf》由会员分享，可在线阅读，更多相关《交通网络最短路径标号算法的实现与效率分析.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第10卷 第9期2005年9月中国图象图形学报Journal of I mage and GraphicsVol.10,No.9Sep.,2005基金项目:国家自然科学基金项目(40201043);中国科学院知识创新工程前沿项目(CXI OG2D04202)收稿日期:2004209206;改回日期:2005201225第一作者简介:陈洁(1982),女。2004年获中国地质大学(武汉)学士学位,现为中国科学院资源与环境信息系统国家重点实验室硕士研究生。主要从事空间数据库技术和城市交通网络分析算法研究。E2mail:交通网络最短路径标号算法的实现与效率分析陈 洁 陆 锋(中国科学院地理科学与资源

2、研究所资源与环境信息系统国家重点实验室,北京 100101)摘 要 标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种Dijkstra算法为核心的标号设定算法是各种商用GIS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法 基于逼近桶结构和改进四叉堆的Dijkstra算法(D IKBA与D IKQH)以及Pallottino算法(T WO-Q

3、),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。关键词 最短路径算法 标号算法 复杂度 交通网络中图法分类号:TP302.7P208 文献标识码:A 文章编号:100628961(2005)0921134205I mplementation and Evaluation of the Shortest Path LabelingAlgo

4、rithm s in Transportation NetworksCHEN Jie,LU Feng(LERIS,Institute of Geographic Sciences and Natural Resources Research,CAS,Beijing100101)AbstractLabeling algorithms have got broad applications for shortest path finding in transportation net works,amongwhich various fine2tunned Dijkstras algorithms

5、well known as typical label setting algorithms have been selected by manyGIS related soft ware for network analysis.However,label correcting algorithms,the other group in label algorithms family,are rarely used yet in GIS net work analysis.After detailed discussion on the structuresof labeling algor

6、ithms,in thispaper,the implementation,complexity and applicabilityof labeling setting and label correcting algorithms are analyzed.Then threebest2known fastest label algorithms,i.e.,Dijkstra algorithm implemented with approximate buckets(D IKBA),Dijkstrasalgorithm based on quad2heap priority queue(D

7、 IKQH)and Pallottino algorithm(T WO-Q),were used to carryoutpracticalevaluation on three real urban road networks.The results showed that for one2to2one shortest path calculation,D IKQH andD IKBA greatly outperformed than T WO2Q algorithm,and D IKQH exhibited the best running efficiency.For one2to2a

8、llshortest path calculation,however,T WO2Q algorithm runs a little faster than D IKQH and D IKBA on the selected real roadnetworks.The author argued thatmore attention should be paid on T WO2Q algorithm for its efficiency and applicability.Keywordsshortest path algorithms,label algorithms,complexity

9、,transportation networks1 引 言交通网络是最短路径算法的主要应用领域,相关研究层出不穷,其各种最短路径算法的分析评述可参见文献16。众所周知,最短路径算法是资源分配、路线设计及分析等优化问题的基础,而交通网络分析中的其他问题,如最可靠路径问题、最大容第9期陈 洁等:交通网络最短路径标号算法的实现与效率分析1135量路径问题、各种各样的路径导航问题也都可以归并到最短路径问题类型中2。标号算法(labelingalgorithms)是最短路径算法族中的重要成员,按照不同的标识结点处理策略,标号算法又可分为标号设定(label setting,简称LS)和标号改正(labe

10、lcorrecting,简称LC)两大体系。对于LS算法,国内外专家学者进行了大量研究。GIS软件产品中的网络分析模块也多是基于LS算法实现,如各种改进的Dijkstra算法79。对于LC算法,一般认为该算法的最大优势是可接受网络负权边,但对于交通网络而言,由于无论以距离、时间和费用作为权值,一般都不存在负权边,加之LC算法较之LS算法复杂难懂,因而LC算法长期以来并未得到重视,而且在商用GIS软件平台中也鲜有应用。据有关研究结果表明,对于不同网络形式,各种算法效率差异很大,也没有一种算法针对各种网络形式均有较好的效率4。为了寻求一种较好的算法,以用于交通网络分析,本文针对交通网络,对LS算法

11、族和LC算法族在时间复杂度、空间复杂度、易实现性、运行效率和算法适用性等方面存在什么样的差异,以及如何有针对性地选择合适的路径算法等问题进行了讨论。2 标号算法分类与算法描述由于问题特征、网络特性等的纷繁复杂,因此最短路径算法表现出多样性。总的来说,最短路径算法可 按问题类 型、网 络 特征 和求 解 技 术 进 行分类6。最短路径算法按求解技术进行分类时,其中路径搜索技术中的通用技术是最短路径算法研究的重点所在,而标号算法就是路径搜索通用技术分类中组合技术的主要算法类型,它也是绝大多数最短路径算法的核心部分。2.1 标号设定与标号改正算法LS算法最早由荷兰数学家Dijkstra于1959年提

12、出,它是理论上最完善、迄今为止应用最广的非负权值网络最短路径算法10。LS算法中的Dijkstra算法的广泛应用,使之成为LS算法的代名词11,而其他LS算法多为Dijkstra算法的不同实现方式,其中基于堆结构和桶结构优先级队列的LS算法是研究得最深入、应用也最广泛的LS算法。针对网络中可能存在负权边的问题,LC算法采用不同的启发式策略,其代表性算法包括Bellman2Ford2Moore算法(即queue算法)、DEsopo2Pape算法(即deque算法)、Pallottino算法(即2 queue算法或T WO-Q算法)1、门限算法12、拓扑排序算法13和SLF(s mall labe

13、l to the front)算法11 等等。实际上,所有的LS或LC算法都可归结为一种更为一般性的算法的特例。它们的不同之处在于对结点扫描的次数以及处理图中所标识结点时采用的优先级队列系统各不相同。2.2 标号算法描述单源最短路径标号算法的标号特征如下:设G=(V,E)是一个有向图,其中,V为结点集合,E为边集合。对于图中结点集合V中每一个结点j,赋予以下两个数值(即“标号”):一个是距离标号d j,其记录的是从起点到该结点的最短路径长度的上界;另一个是前驱标号p j,其记录的是当起点s到该结点j的一条路径长度取到该上界时,该条路径中结点j的直接前驱结点。这样,算法通过不断修改这些标号来进行

14、迭代计算,即可求解最短路径。迭代计算的过程中,所有结点实际上被分成了以下两类:一类是离起点s较近的结点,它们的距离标号表示的是从点s到该结点的最短路径长度,其标号不会在以后的迭代中再被改变,故称为永久标号;另一类是离起点s较远的结点,它们的距离标号表示的只是从点s到该结点的最短路径长度的上界,由于其标号还可能会在以后的迭代中再被改变,因此称为临时标号。标号算法的目的就是在算法结束时,将所有的临时标号都转变为永久标号。这时,距离标号表示的就是从起点到该结点的最短路径长度。LS算法通过迭代过程对标号进行逐步修正,每次迭代均选择候选结点集合中的标号最小者,然后将其退出候选结点集,并将该结点标号从临时

15、标号转变为永久标号。这是一种基于贪心策略的最短路径算法,其要求在路径选择中的每一步所选择的路径都是到目前为止最好的,以起点至当前结点路径权值之和作为贪心选择策略,在“局部最优而导致总体最优”的假设下,寻求最佳路径。LC算法在每次迭代时,并不一定将任何结点标号都从临时标号转变为永久标号,只是对临时标号进行一次修正,而其所有结点标号仍然为临时标号,1136中国图象图形学报第10卷只有在所有迭代终止时,才将所有结点标号同时转变为永久标号。LC算法考虑的是“最终最优”,因此最短路径需要等待多次迭代,直到整个算法运行结束才能被确定。3 标号算法流程及复杂度分析LS算法的执行流程如下:(1)初始化。令集合

16、S=,S的补集S=V,d s=0,p s=-1;对V中的结点j(j|S),令其初始距离标号d j=;(2)如果S=V,则d j为起点s到结点j的最短路径长度,其最短路径可以通过前驱标号p j所记录的信息反向追踪获得,结束,否则继续步骤3;(3)从S中找到距离标号最小的结点i,把它从S中 删 除,加 入S。对 于 所 有 从i出 发 的 弧(i,j)E,其弧长为li,j,若d jd i+li,j,则令d j=d i+li,j,p j=i,转步骤2。该算法的主要计算量在于步骤3循环。它包括以下两个过程:结点寻找过程(从S中找到距离标号最小的结点i)和距离修改过程(修改与结点i相邻的结点的距离标号)

17、。若以n表示网络结点数、以m表示弧段数(下同),则在不引入任何优先级队列结构的情况下,传统的单源Dijkstra算法对于结点寻找过程,第1次循环时,需要n次比较操作;第2次循环时,需要n-1次比较操作,依次类推,若以T(n)表示最坏情况的运行时间,以O记号给出函数T(n)的上界10(下同),则该过程的复杂度为T(n)=n+(n-1)+1=O(n2)。对于距离修改过程,由于其整体效应相当于对每条弧进行一次检查,因此该过程复杂度为O(m),而该算法的时间复杂度为O(n2+m)=O(n2)。对于稠密网络,这是求解单源最短路径问题可能达到的最小的复杂度14。对于稀疏网络,若利用各种形式的优先级队列(如

18、堆、桶等)来改进算法的运行结构,则算法的时间复杂度可不同程度地降低,例如,基于K叉堆的单源Dijkstra算法的复杂度为O(mlogn),基于桶结构的单源Dijkstra算法的复杂度为O(m+nC)(其中C为常量)等等。LC算法的执行流程如下:(1)令距离标号ds=0,前驱标号ps=-1;对其他的结点j,令初始距离标号d j=;(2)如果对所有的弧(i,j),有d jd i+li,j,则结束,d j就是从起点s到结点j的最短路径长度,即最短路径可以通过前驱标号获得,否则进入步骤3;(3)找到一条满足d jd i+li,j的弧(i,j),令d j=d i+li,j,p j=i,则转步骤2。算法的

19、总时间复杂度为O(n2m)。对比上述LS与LC算法执行流程可以看出:由于LS算法在候选结点集处理的每一步,都能得到一条由源点到其余结点的最短路径,因此在进行11路径搜索时,当终点跳出候选结点集时即可结束,但由于每个结点在整个算法运行过程中只进出候选集一次,因此LS算法不能处理含负权边的网络,而一般只能用来求解无圈网络和正费用网络的最短路径问题。LC算法在处理结点时,可能需要多次进出优先级队列,因此起点到终点的11最短路径需要等到算法全部结束才能得到。值得说明的是,结点多次出入优先级队列是为了完成结点距离标号的多次迭代计算,这使得LC算法摆脱了LS算法对于网络非负权边的约束,因而其可以处理含负权

20、边的网络,即对于一般费用网络的最短路问题均适用。长期以来,专家学者们对LS和LC算法的效率比较进行了深入的研究。文献12 认为,对于稠密图,Dantzig算法优于DEsopo2Pape算法;而对于稀疏图,虽然有指数形式的最坏时间界,DEsopo2Pape算法仍然是最优的12。文献 3 的研究结果也表明,DEsopo2Pape算法可与最好的LS算法相媲美3。文献4 的研究结果表明,对于不同的网络形式,不仅各种算法效率差异很大,而且没有一种算法针对各种网络形式均有较好的效率,例如对于矩形规则格网型网络,LC算法中的Pape算法和2que算法效率最高;对于稠密网络,双桶Dijkstra算法(即D I

21、KBD(dijkstras algorithm implemented withdouble bucket)算法)和门限算法效率最高;对于非平面的规则格网型网络,D IKBD算法和堆结构的Dijkstra算 法(即D IKH(dijkstrasalgorithmimplemented with heap)算法)效率最高;对于无环图,D IKBD算法和拓扑排列算法效率最高4。值得注意的是,理论上最优的算法不一定在实践中最优。总的来说,基于逼近桶结构的Dijkstra算法(即D IKBA(dijkstras algorithm implementedwith approximate bucket)

22、算法)4、基于改进四叉堆第9期陈 洁等:交通网络最短路径标号算法的实现与效率分析1137结构的Dijkstra算法(即D IKQH(dijkstras algorithmimplemented with quad heap)算法)7 和Pallottino算法(即T WO-Q算法)4 分别是LS算法和LC算法中公认的最为优秀的算法,其时间复杂度分别为O(m+n(+C/)、O(nlogn)和O(n2m)。本文结合3套城市交通网数据分别测试这3种算法在11、1N最短路径搜索中的运行效率,并将实验结果与理论分析结果进行了对照。4 标号算法在城市交通网络中的运行效率比较4.1 运行环境实验中的算法代码

23、均使用标准C语言编写,在P4 218G CPU、512M内存的PC硬件环境、VC+610编译环境中经调试编译通过。为了比较不同标号算法的运行效率,本文选用3套城市交通网数据作为实验交通网络(网络基本信息如表1所示)进行了试验对比,计算中,以弧段长度作为边权值。表1 实验交通网络Tab.1Characteristics of real2world networks i n the study实验网络结点数弧段数A12 80318 107B11 89316 689C4 8937 9244.2 效率比较与分析各算法的实际运行时间均指执行算法的CPU耗时,而不包括数据输入和输出等操作占用的时间。对于各

24、实验网络,在做11时间统计时,采取系统抽样方法从网络中选取100个结点作为起点、100个结点作为终点,以保证被选取的结点能覆盖整个网络。求解最短路径时,首先分别统计这100个起点中每个结点到每个终点的11最短路径的运行时间,然后对所有的11耗时求取平均值;在做1N时间统计时,首先对网络中每个结点分别统计其搜索所有结点所需的时间开销,然后对所有结点的1N耗时求取平均值。各算法耗时统计结果如图1所示。由图1明显可见,以城市交通网A、B、C为实验网络,当执行11路径搜索时,LS算法族中的D IKBA算法和D IKQH算法,由于允许到达搜索的终止结点后即可退出算法循环,因此运行效率均明显高于LC算法族

25、中的T WO-Q算法。由于运行T WO-Q算法时,必须等待算法全部结束才能跳出,因此,对于同一网络,11搜索和1N搜索的CPU耗时相同。当执行1N最短路径搜索时,3种算法的实际运行效率的相对差异发生了较大改变,其中,在交通网络A和B中,T WO-Q算法运行效率最高,而D IKQH算法次之,D IKBA算法最低;在交通网络C中,D IKQH算法运行效率跃升至最高,T WO_Q算法次之,D IKBA算法依然最低。图1T WO-Q算法、D IKQH算法、D IKBA算法路径搜索CPU耗时(ms)Fig.1Consumed CPU ti me(ms)of T WO-Q,D IKQH,D IKBA al

26、gorithm in shortest path searching1138中国图象图形学报第10卷 根据上一节对LS算法和LC算法的时间复杂度的理论分析,D IKBA算法的最坏时间复杂度为O(m+n(+C/),而T WO-Q算法的最坏时间复杂度为O(n2m),可见T WO-Q算法的时间复杂度远大于D IKBA算法。然而,在实际运行过程中,算法的运行效率与所选网络的具体特征关系密切,其运行效率的高低并不一定与与理论上的时间复杂度保持一致性关系,这是需要引起高度注意的地方。5 结 论据本文研究与实验过程可以得出以下结论:(1)在交通网络最短路径搜索中,当处理11最短路径搜索时,LS算法允许搜索到

27、终止结点即可退出运算过程,而LC算法则需要完成全部结点的最短路径搜索才能得到11的最短路径。LS算法族中最优秀的D IKBA算法和D IKQH算法较之LC算法族中最优秀的T WO-Q算法效率高。由于D IKBA算法要求整数权值,因此对于以长度、时间或者费用等浮点类型的权值需要做整型化处理,而且由于采用以权值为地址的桶运行结构,因而使得D IK BA算法的空间复杂度较之D IKQH算法略大,算法结果也存在一定的误差。在1N最短路径搜索中,T WO-Q算法与D IKQH算法效率接近,T WO-Q算法略快。而D IKBA算法较之T WO-Q算法与D IK QH算法略差。(2)LS算法族与LC算法族优

28、点各异,其中,LC算法族中的T WO-Q算法既允许网络中存在负权边,又不会对边造成权值精度损失,而且其1N路径搜索效率高于LS算法族中的最优算法具有可比性。此外,由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且LC算法族中的T WO-Q算法较之LS算法族中最优的D IKBA算法和D IKQH算法具有更大的适用范围,因此其在交通网络路径分析具有极大的应用潜力。参考文献(References)1Pallotlino S.Shortest path methods:complexity,interrelation andnew propositionsJ.Networks,1984,14

29、:257267.2Deo N,PangC Y.Shortest2path algorithms:taxonomy and annotationJ.Networks,1984,14:275323.3Gallo G,Pallottino S.Shortest paths algorithms J.Annals ofOperations Research,1988,13:379.4Cherkassky B V,Goldberg A V,RadzikT.Shortest pathsalgorithms:theory and experimental evaluation J.MathematicalP

30、rogramming,1996,73:129174.5Zhan F B,Noon C E.Shortest path algorithms:an evaluation usingreal road networks J.Transportation Science,1998,32(1):6573.6Lu Feng.Shortestpath algorithms:taxonomy and advance in researchJ.ACTA GEODAETICA et CARTOGRAPHI CA SI N ICA,2001,30(3):269275.陆锋.最短路径算法:分类体系与研究进展J.测绘

31、学报,2001,30(3):269275.7Lu Feng,Lu Dong2mei,CuiWei2hong.I mproved Dijkstra algorithmbased on quad2heap priority queue and inverse adjacent list J.Journal of I mage and Graphics,1999,4A(12):10441050.陆锋,卢冬梅,崔伟宏.基于四叉堆优先级队列及逆邻接表的改进型Dijkstra算 法 J.中 国 图 象 图 形 学 报,1999,4A(12):10441050.8Yue Yang,GongJian2ya.A

32、n efficient implementation of shortestpathalgorithm based on Dijkstras algorithm J.Journal of WuhanTechnical University of Surveying and Mapping,1999,24(3):209212.乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现J.武汉测绘科技大学学报,1999,24(3):209212.9Wang Kai2yi,Zhao Chun2jiang,Xu Gui2xian,et al.Ahigh2efficiency realization w

33、ay of the shortest path search problem in GISfieldJ.Journal of I mage and Graphics,2003,8A(8):951956.王开义,赵春江,胥桂仙等.GIS领域最短路径搜索问题的一种高效实现J.中国图象图形学报,2003,8A(8):951956.10 Pan Jin2gui,GU Tie2cheng,Zeng Jian,et al.Common data structureand algorithmsofmodern computerM.Nanjing:Nanjing UniversityPress,1994.潘金

34、贵,顾铁成,曾俭等编译.现代计算机常用数据结构和算法M.南京:南京大学出版社,1994.11 Bertsekas D P.A simple and fast label correcting algorithm forshortest pathsJ.Network,1993,23:703709.12 Glover F,Glover R,Klingman D.Computational study of animproved shortest path algorithmJ.Networks,1984,14:2536.13 GoldbergA V,Radzik T.A heuristic improvement of the Bellman2Ford algorithm J.Applied Mathematics Letters,1993,6(3):36.14 Xie Jin2xing,Xing Wen2xun.Network optimization M.Beijing:Tsinghua UniversityPress,2000.谢金星,邢文训编著.网络优化M.北京:清华大学出版社,2000.