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

10920059JournalofImageandGraphicsVol.10,No.9Sep.,2005:(40201043);(CXIOG2D04202):2004209206;:2005201225:(1982),2004(),E2mail:[e-mail](,100101),DijkstraGIS,,;,Dijkstra(DIKBADIKQH)Pallottino(TWO-Q),;,,,;,,:TP302.7P208:A:100628961(2005)0921134205ImplementationandEvaluationoftheShortestPathLabelingAlgorithmsinTransportationNetworksCHENJie,LUFeng(LERIS,InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,Beijing100101)AbstractLabelingalgorithmshavegotbroadapplicationsforshortestpathfindingintransportationnetworks,amongwhichvariousfine2tunnedDijkstrasalgorithmswellknownastypicallabelsettingalgorithmshavebeenselectedbymanyGISrelatedsoftwarefornetworkanalysis.However,labelcorrectingalgorithms,theothergroupinlabelalgorithmsfamily,arerarelyusedyetinGISnetworkanalysis.Afterdetaileddiscussiononthestructuresoflabelingalgorithms,inthispaper,theimplementation,complexityandapplicabilityoflabelingsettingandlabelcorrectingalgorithmsareanalyzed.Thenthreebest2knownfastestlabelalgorithms,i.e.,Dijkstraalgorithmimplementedwithapproximatebuckets(DIKBA),Dijkstrasalgorithmbasedonquad2heappriorityqueue(DIKQH)andPallottinoalgorithm(TWO-Q),wereusedtocarryoutpracticalevaluationonthreerealurbanroadnetworks.Theresultsshowedthatforone2to2oneshortestpathcalculation,DIKQHandDIKBAgreatlyoutperformedthanTWO2Qalgorithm,andDIKQHexhibitedthebestrunningefficiency.Forone2to2allshortestpathcalculation,however,TWO2QalgorithmrunsalittlefasterthanDIKQHandDIKBAontheselectedrealroadnetworks.TheauthorarguedthatmoreattentionshouldbepaidonTWO2Qalgorithmforitsefficiencyandapplicability.Keywordsshortestpathalgorithms,labelalgorithms,complexity,transportationnetworks1,,[16],,,9:1135[2](labelingalgorithms),,(labelsetting,LS)(labelcorrecting,LC)LS,GISLS,Dijkstra[79]LC,,,,,LCLS,LC,GIS,,,[4],,,LSLC,2,,[6],,,2.1LSDijkstra1959,[10]LSDijkstra,LS[11],LSDijkstra,LSLS,LC,Bellman2Ford2Moore(queue)DEsopo2Pape(deque)Pallottino(2queueTWO-Q)[1][12][13]SLF(smalllabeltothefront)[11],LSLC2.2:G=(V,E),,V,EVj,():d[j],;p[j],sj,j,,,:s,s,,;s,s,,,,LS,,,,,,,LC,,,,113610,LC,,3LS:(1)S=Á,SS=V,d[s]=0,p[s]=-1;Vj(j|S),d[j]=;(2)S=V,d[j]sj,p[j],,3;(3)Si,S,Si(i,j)E,li,j,d[j]d[i]+li,j,d[j]=d[i]+li,j,p[j]=i,23:(Si)(i)nm(),,Dijkstra,1,n;2,n-1,,,T(n),OT(n)[10](),T(n)=n+(n-1)++1=O(n2),,O(m),O(n2+m)=O(n2),[14],(),,,KDijkstraO(mlogn),DijkstraO(m+nC)(C)LC:(1)d[s]=0,p[s]=-1;j,d[j]=;(2)(i,j),d[j]d[i]+li,j,,d[j]sj,,3;(3)d[j]d[i]+li,j(i,j),d[j]=d[i]+li,j,p[j]=i,2O(n2m)LSLC:LS,,11,,,LS,LC,,11,,LCLS,,,LSLC[12],,DantzigDEsopo2Pape;,,DEsopo2Pape[12][3],DEsopo2PapeLS[3][4],,,,,LCPape2que;,Dijkstra(DIKBD(dijkstrasalgorithmimplementedwithdoublebucket));,DIKBDDijkstra(DIKH(dijkstrasalgorithmimplementedwithheap));,DIKBD[4],,Dijkstra(DIKBA(dijkstrasalgorithmimplementedwithapproximatebucket))[4]9:1137Dijkstra(DIKQH(dijkstrasalgorithmimplementedwithquadheap))[7]Pallottino(TWO-Q)[4]LSLC,O(m+n(+C/))O(nlogn)O(n2m)33111N,44.1C,P4218GCPU512MPCVC++610,3(1),,1Tab.1Characteristicsofreal2worldnetworksinthestudyA1280318107B1189316689C489379244.2CPU,,11,100100,,10011,11;1N,,1N11,ABC,11,LSDIKBADIKQH,,LCTWO-QTWO-Q,,,,111NCPU1N,3,,AB,TWO-Q,DIKQH,DIKBA;C,DIKQH,TWO_Q,DIKBA1TWO-QDIKQHDIKBACPU(ms)Fig.1ConsumedCPUtime(ms)ofTWO-Q,DIKQH,DIKBAalgorithminshortestpathsearching113810LSLC,DIKBAO(m+n(+C/)),TWO-QO(n2m),TWO-QDIKBA,,,,5:(1),11,LS,LC11LSDIKBADIKQHLCTWO-QDIKBA,,,DIKBADIKQH,1N,TWO-QDIKQH,TWO-QDIKBATWO-QDIKQH(2)LSLC,,LCTWO-Q,,1NLS,,LCTWO-QLSDIKBADIKQH,(References)1PallotlinoS.Shortestpathmethods:complexity,interrelationandnewpropositions[J].Networks,1984,14:257267.2DeoN,PangCY.Shortest2pathalgorithms:taxonomyandannotation[J].Networks,1984,14:275323.3GalloG,PallottinoS.Shortestpathsalgorithms[J].AnnalsofOperationsResearch,1988,13:379.4CherkasskyBV,GoldbergAV,RadzikT.Shortestpathsalgorithms:theoryandexperimentalevaluation[J].MathematicalProgramming,1996,73:129174.5ZhanFB,NoonCE.Shortestpathalgorithms:anevaluationusingrealroadnetworks[J].TransportationScience,1998,32(1):6573.6LuFeng.Shortestpathalgorithms:taxonomyandadvanceinresearch[J].ACTAGEODAETICAetCARTOGRAPHICASINICA,2001,30(3):269275.[.:[J].,2001,30(3):269275.]7LuFeng,LuDong2mei,CuiWei2hong.ImprovedDijkstraalgorithmbasedonquad2heappriorityqueueandinverseadjacentlist[J].JournalofImageandGraphics,1999,4A(12):10441050.[,,.Dijkstra[J].,1999,4A(12):10441050.]8YueYang,GongJian2ya.AnefficientimplementationofshortestpathalgorithmbasedonDijkstrasalgorithm[J].JournalofWuhanTechnicalUniversityofSurveyingandMapping,1999,24(3):209212.[,.Dijkstra[J].,1999,24(3):209212.]9WangKai2yi,ZhaoChun2jiang,XuGui2xian,etal.Ahigh2efficiencyrealizationwayoftheshortestpathsearchprobleminGISfield[J].JournalofImageandGraphics,2003,8A(8):951956.[,,.GIS[J].,2003,8A(8):951956.]10PanJin2gui,GUTie2cheng,ZengJian,etal.Commondatastructureandalgorithmsofmoderncomputer[M].Nanjing:NanjingUniversityPress,1994.[,,.[M].:,1994.]11BertsekasDP.Asimpleandfastlabelcorrectingalgorithmforshortestpaths[J].Network,1993,23:703709.12GloverF,GloverR,KlingmanD.Computationalstudyofanimprovedshortestpathalgorithm[J].Netwo