Dijkstra最短路径算法的一种高效率实现(4)

Dijkstra最短路径算法的一种高效率实现

图3　GeoStar中最佳路径实现示意图

Fig.3　TheShortestPathinGeoStar

参考文献

1　ZhanFB.ThreeFastestShortestPathAlgorithms

.JournalofGeographicIn2onRealRoadNetworks

集.武汉:武汉测绘科技大学出版社,1997

3　卢开澄,卢华明.图论及其应用(第二版).北京:清华

大学出版社,1997

4　严蔚敏,吴伟民.数据结构.北京:清华大学出版社,

1997

5　米涅卡E.网络和图的最优化算法.李家滢,赵关旗

～formationandDecisionAnalysis,1997,1(1):69

82

2　丁跃民.GIS中实用空间算法设计的关键技术.见:地

译.北京:中国铁道出版社,1984

理信息系统软件工程及其相关技术高级研讨会论文

AnEfficientImplementationofShortestPathAlgorithm

BasedonDijkstraAlgorithm

YueYang　GongJianya

(NationalLaboratoryforInformationEngineeringinSurveying,MappingandRemoteSensing,

WTUSM,129LuoyuRoad,Wuhan,China,430079)

Abstract　WiththedevelopmentofgeographicinformationscienceandthewideuseofGISsoftware,moreandmoreneedsarerequiredtothenetworkanalyses.Asthekeyofnetworkanalyses,computingtheshortestpathsoveranetworkisanimportantproblemthatscholarsfacuson.StartwiththedatastructureduringitscomputationprocessandcombinedwithF.BenjaminZhan’sevaluationofasetof15shortestpathalgorithms,thispaperpresentsanefficientmethodofrealizetheshortestpathalgorithmwhichisbasedonDijkstraalgorithm.Resultshowsthatthismethodperformswellinpractice.Keywords　shortestpathalgorithm;networkanalysis;GIS