搜索
303Vol.30,No.320018ACTAGEODAETICAetCARTOGRAPHICASINICAAug.,2001:1001-1595(2001)03-0269-07:P208:A:陆 锋(,100101)ShortestPathAlgorithms:TaxonomyandAdvanceinResearchLUFeng(StateKeyLaboratoryofResourceandEnvironmentInformationSystem,ChineseAcademyofSciences,Bei-jing100101,China)Abstract:Theshortestpathproblemisaresearchtopicinthefieldofgeographicinformationscienceandcomputerscience.Inthispaper,theauthordiscussedthetaxonomyoftheshortestpathalgorithmsfromproblemtype,networkcharacteristicsandsolutiontechniques,comparedthetimecomplexitiesofthosecom-monusedsequentialshortestpathalgorithmsandevaluatedtherelevantresearches.Themostpopularse-quentialshortestpathalgorithmsareevaluatedfortheirpracticalefficiencywithurbantrafficnetworks.Theadvanceoftime-dependantandparallelshortestpathalgorithmsisalsodiscussed.Keywords:shortestpathalgorithms;taxonomy;evaluation;advance:最短路径算法是计算机科学与地理信息科学等领域的研究热点。本文首先讨论了平面图的搜索策略,然后从问题类型、网络类型和实现方法3方面对最短路径算法进行了系统的分类,从理论上比较了近年来所提出的各种具有较高效率的串行最短路径算法的时间复杂度,并对国内外一些相关研究进行了综合评述。结合城市交通网络的实验结果,作者对几种应用最为广泛的串行最短路径算法的运行效率进行了分析和评价,最后对最短路径算法在实时化和并行化方面的发展进行了讨论。:2000-06-30;:2000-11-16:(96-B02-03-05):(1970-),,,,:最短路径算法;分类;评价;进展1 前 言[13],[1],[2,46],;,[7],;,[8][9][10];[11],;,[12,13],,,,2 图的搜索策略3[14],,,Small-WorldNetworks[15][16],,[8,10,17]3,OPEN[14],[18],,,,,Dijkstra,Dijkstra[14,17]3 最短路径算法分类体系,,3.1,5,k,11Fig.1Classificationsystemfortheshortestpathalgorithmsbyproblemtype3.2,2270302Fig.2Classificationsystemfortheshortestpathalgorithmsbynetworkcharacteristics,,O(1)(i,j),,O(n),O(n2),10000,100M,[19][20],,,,[20],,,,,,,,,ForwardStar(FS)Back-wardStar(BS)[1,21,22],O(e/n),(enn(n-1)/2),O(e+n),,,[2,5,6,8,10,18,23,24]3.332(LabelingAlgorithms)[23,24],(LabelSetting,LS)(LabelCorrecting,LC)2713::3Fig.3ClassificationsystemfortheshortestpathalgorithmsbysolutiontechniquesLS,Dijkstra1959LSLSDijkstraLS[4]LSDijkstra,Dijkstra,[5],[18],Dijkstra,O(n2),104104*104Dijkstra,,DijkstraO(n2)kFibonacciDijkstra,O(mlogn)O(m+nlogn)[25,26],Dijkstra,,O(m+nlogC/loglogC)(C),FDijkstraO(m+n(logC)1/2)[7][9]DijkstraO(n3),,LCBellman-Ford-Moore(queue)D'Esopo-Pape(deque)Pallottino(2que)[27][28][29]SLF[4],LSLC[21,27]LS,,11,LS;LC,,11LC,LSLC[28],,DantzigD'Esopo-Pape;,,D'Esopo-Pape[28][23]D'Esopo-PapeLS[23][2],,,,LCPape2que27230;,Dijkstra(DIKBD);,DIKBDDijkstra(DIKH);,DIKBD[2],,[25]Fibonac-ciDijkstra(DIKF)DIKH[25],,DIKHDIKF[2,26]4 交通网络最短路径算法效率比较GIS,[3,5,6,811,18,20,30],,Dijkstra,Arc/InfoNet-workDikstra;GeostarFIFODijkstra[6];[5]Dijkstra,,[5]0.1s(12800,17800,PentiumPro200,32M)[5]ArcView3.0aNetworkAnalysis,,ArcView10s[9],MapInfo,ArcViewMapInfo[18],,,,[3]15,,1n,LC2que,LSDIKBDDIKBA[3][2][23][2][23][24],,,DIKBDDIKBA(Dijk-stra),[2][010000],[3],1n,DIKBADIKBD,2queDIKBA50%,[3],11,2queDIKBA,14%[30][8][10],[5],[9],,5 最短路径算法研究发展方向5.1,,,,,t,[31],[21]FIFO,LSLC[22][21]2733::Chrono-SPT,,,,FIFO,[31],,3[31][13],O(n2)[13]5.2,,[12,13],,,,,;,(),,,参考文献:[1]DEON,PANGCY.ShortestPathAlgorithms:TaxonomyandAnnotation[J].Networks,1984,14:275-323.[2]CHERKASSKYBV,GOLDBERGAV,RADZIKT.ShortestPathsAlgorithms:TheoryandExperi-mentalEvaluation[J].MathematicalProgram-ming,1996,73:129-174.[3]ZHANFB,NOONCE.ShortestPathAlgo-rithms:AnEvaluationUsingRealRoadNetworks[J].TransportationScience,1998,32(1):65-73.[4]BERTSEKASDP.ASimpleandFastLabelCor-rectingAlgorithmforShortestPaths[J].Net-works,1993,23:703-709.[5]LUFeng,LUDong-mei,CUIWei-hong.ImprovedDijkstra'sAlgorithmBasedonQuad-heapPriorityQueueandInverseAdjacentLists[J].JournalofImageandGraphics,1999,4A(12):1039-1045.(inChinese)[6]YUEYang,GONGJian-ya.AnEfficientImple-mentationofShortestPathAlgorithmBasedonDijkstraAlgorithm[J].JournalofWuhanTechni-calUniversityofSurveyingandMapping,1999,24(3):209-212.(inChinese)[7]AHUJARK,MEHLHORNK,ORLINJB,etal.FasterAlgorithmsfortheShortestPathProblem[J].JournaloftheAssociationforComputingMa-chinery,1990,37(2):213-223.[8]LUFeng,LUDong-mei,CUIWei-hong.TimeShortestPathAlgorithmforRestrictedSearchingAreainTransportationNetworks[J].JournalofImageandGraphics,1999,4A(10):849-853.(inChinese)[9]YANHan-bing,LIUYing-chun.ANewAlgo-rithmforFindingShortcutinaCity'sRoadNetBasedonGISTechnology[J].ChineseJournalofComputers,2000,23(2):210-225.(inChinese)[10]LUFeng,ZHOUCheng-hu,WANQin.AnOp-timumPathAlgorithmforTrafficNetworkBasedonHierarchicalSpatialReasoning[J].Geo-spatialInformationScience,2000,3(4):36-42.[11]HUANGY,JINGN,RUNDENSTEINEREA.AHierarchicalPathViewModelforPathFindinginITS[J].Geoinformatica,1997,1(2):125-159.[12]HENZINGERMR,KLEINP,RAOS,etal.FasterShortest-pathAlgorithmsforPlanarGraphs[J].JournalofComputerandSystemSci-ences,1997,55(1):3-23.[13]MAJun,MAShao-han.TheAlgorithmsforComputingandUpdatingtheShortestTrees[J].ComputerResearch&Development,1995,32(12):45-49.(inChinese)[14]NILSSONNJ.ArtificialIntelligence:ANewSynthesis[M].Beijing:ChinaMachinePress,1999.[15]WATTSDJ,STROGATZSH.CollectiveDy-namicsofSmall-worldNetworks[J].Nature,1998,393(4):440-442.[16]JIANGB,CLARAMUNTC,BATTYM.Geo-metricAccessibilityandGeographicInformation:ExtendingDesktopGIStoSpaceSyntax[J].ComputerEnvironmentandUrbanSystems,274301999,23(2):127-146.[17]FISHERPF