资源描述：
《交通网络最短路径标号算法的实现与效率分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第10卷第9期中国图象图形学报Vol.10,No.92005年9月JournalofImageandGraphicsSep.,2005交通网络最短路径标号算法的实现与效率分析陈洁陆锋(中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101)摘要标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种Dijkstra算法为核心的标号设定算法是各种商用GIS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的
2、基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的Dijkstra算法(DIKBA与DIKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析
3、中具有极大的应用潜力。关键词最短路径算法标号算法复杂度交通网络中图法分类号:TP302.7P208文献标识码:A文章编号:100628961(2005)0921134205ImplementationandEvaluationoftheShortestPathLabelingAlgorithmsinTransportationNetworksCHENJie,LUFeng(LERIS,InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,Beijing100101)Abst
4、ractLabelingalgorithmshavegotbroadapplicationsforshortestpathfindingintransportationnetworks,amongwhichvariousfine2tunnedDijkstra’salgorithmswellknownastypicallabelsettingalgorithmshavebeenselectedbymanyGISrelatedsoftwarefornetworkanalysis.However,labelcorrectingalgorithm
5、s,theothergroupinlabelalgorithmsfamily,arerarelyusedyetinGISnetworkanalysis.Afterdetaileddiscussiononthestructuresoflabelingalgorithms,inthispaper,theimplementation,complexityandapplicabilityoflabelingsettingandlabelcorrectingalgorithmsareanalyzed.Thenthreebest2knownfaste
6、stlabelalgorithms,i.e.,Dijkstraalgorithmimplementedwithapproximatebuckets(DIKBA),Dijkstra’salgorithmbasedonquad2heappriorityqueue(DIKQH)andPallottinoalgorithm(TWO-Q),wereusedtocarryoutpracticalevaluationonthreerealurbanroadnetworks.Theresultsshowedthatforone2to2oneshortes
7、tpathcalculation,DIKQHandDIKBAgreatlyoutperformedthanTWO2Qalgorithm,andDIKQHexhibitedthebestrunningefficiency.Forone2to2allshortestpathcalculation,however,TWO2QalgorithmrunsalittlefasterthanDIKQHandDIKBAontheselectedrealroadnetworks.Theauthorarguedthatmoreattentionshouldb
8、epaidonTWO2Qalgorithmforitsefficiencyandapplicability.Keywordsshortestpathalgorithms,labelalgori
