一种基于Dijkstra并行线程算法的研究与实现-论文.pdf

《一种基于Dijkstra并行线程算法的研究与实现-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第37卷第9期测绘与空间地理信息V01．37．No．92014年9月GEOMATICS＆SPATIALlNFoRMATloNTECHNoLoGySep．，2014一种基于Dijkstra并行线程算法的研究与实现李平，李永树(西南交通大学地球科学与环境工程学院，四川成都610031)摘要：针对传统Dijkstra算法运行效率的问题，提出了一种基于传统Dijkstra并行线程的算法，该算法动态地将交通网络进行子网分割。通过实验测试了不同网络节点数量和弧段数量下传统Dijkstra算法和本文算法运行时间，实验结果表明本文算法能够缩减网

2、络节点搜索空间，降低算法的时间复杂度，提高算法的运行效率。关键词：Dijkstra算法；GIS；多线程；子网；时间复杂度；运行效率中图分类号：P208文献标识码：B文章编号：1672—5867(2014)o9—0050一o4ResearchandImplementationofOneParallelThreadAlgorithmBasedonDijkstraLIPing，LIYong—shu(EarthScienceandEnvironmentalEngineeringAcademyofSouthwestJiaotongUniv

3、ersity，Chengdu610031，China)Abstract：AimingattheproblemofoperatingeficiencyoftraditionalDijkstraalgorithm，thepapercomesupwithonealgorithmofparallelthreadbasedontraditionalDijkstra．Thealgorithmdivisestrafficnetworkintosubnetsdynamically．Throughexperiment，theoperatingti

4、meoftraditionalDijkstraalgorithmistestedunderdifferentnumberofnetworkjunctionsandarCS．Theexperimenthasdemonstratedthatthealgorithmcanlowersearchingspaceofnetworkjunctions，reduceDijkstratimecomplexityandimproveDijkstraoperatingeficiency．Keywords：Dijkstraalgorithm；GIS；

5、muhithreading；subnet；timecomplexity；operatingefficiency度为O(n)，随着网络节点数增加，算法需要的时间也0引言会成倍增加。考虑到没有充分利用现有的计算机资最短路径分析是GIS空间分析中最重要的分析应用源，仍有较大的提升空间。本文提出一种新的并行算法之一，其在医疗救护、火灾救援等事故以及人们出行导航思路，在经典Dijkstra算法的基础上，采用双线程分别从方面已经成为不可或缺的分析应用⋯。随着城市交通网起点和终点同时按照Dijkstra算法最短路径的搜索分析，络的日趋复杂以及

6、用户体验的日益提高，最短路径分析分析过程中采用节点标记法动态地将交通网络进行子网需要在尽可能短的时间分析出结果，加之计算机软硬件分割，最终将两个子网的搜索结果进行拼接汇总，获取最日新月异的进步，使得并行处理分析成为可能。短路径。目前，对于最短路径Dijkstra算法研究主要有两个大1最短路径算法简述的方向：一个是对于经典串行算法Dijkstra的修改、约束和改进，以达到改进经典算法的空间复杂度和时间复杂传统Dijkstra算法思想，被认为是最完备的算法，得度，提高算法的运行效率的目的；另一个是修改Dijkstra出的结果最短，其

7、特点是以起始点为中心，弧段权重为代算法为并行算法，合理利用计算机资源，提高算法的运行价，向外层层扩展，直至扩展到终点为止。效率，较普遍的做法是，先根据并行数进行网络节点的平设G=(，E)是一个赋权有向图，即对于图中的每均分配，然后进行分析处理，但也不是并行数越多，效率一条边e=(，)都赋予了一个权值WD()表示点越高。和vi之间的最短距离。在图G中指定一个顶点，，确经典的Dijkstra算法属于串行算法，该算法时间复杂定为起点。收稿日期：2014一O1—22基金项目：高等学校博士学科点专项科研基金(20100184110019)

8、资助作者简介：李平(1986一)，男，四川绵阳人，地图学与地理信息系统专业硕士研究生，主要研究方向为地理信息系统及其应用。第9期李平等：一种基于Dijkstra并行线程算法的研究与实现511)开始，先给。标上红色标号，且D()=0，其余各点D(vi)=+oo(≠