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

Dijkstra最短路径算法的一种高效率实现*      关键词最短路径算法;网络分析;地理信息系统分类号 P208;O22AnEfficientImplementationofShortestPathAlgorithmBasedonDijkstraAlgorithmYueYang GongJianya(NationalLaboratoryforInformationEngineeringinSurveying,MappingandRemoteSensing,WTUSM,129LuoyuRoad,Wuhan,China,430079)Abstract WiththedevelopmentofgeographicinformationscienceandthewideuseofGISsoftware,sevaluationofasetof15shortestpathalgorithms, workanalysis;GIS 随着计算机的普及以及地理信息科学的发展,GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其他的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及医疗救护系统),这些系统一般要求计算出到出事地点的最佳路线的时间应该在1s~3s内,在行车过程中还需要实时计算出车辆前方的行驶路线,这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低,它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础,只是不同系统对Dijkstra算法采用了不同的实现方法。据统计,目前提出的此类最短路径的算法大约有17种。,结果显示有3种效果比较好,它们分别是:TQQ(graphgrowthwithtwoqueues)、DKA(theDijkstra'salgorithmimplementedwithapproximatebuckets)以及DKD(theDijkstrasalgorithmimplementedwithdoublebuckets),这些算法的具体内容可以参见文献[1]。其中TQQ算法的基础是图增长理论,较适合于计算单源点到其他所有点间的最短距离;后两种算法则是基于Dijkstra的算法,更适