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

《dijkstra 最短路径算法的一种高效率实现-》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Dijkstra最短路径算法的一种高效率实现*摘　要　在已存在的一些最短路径算法测试总结的基础上，根据GIS中网络计算的实际情况，从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手，提出了一种Dijkstra最短路径算法的高效率实现方法。关键词　最短路径算法；网络分析；地理信息系统分类号　P208；O22AnEfficientImplementationofShortestPathAlgorithmBasedonDijkstraAlgorithmYueYang　GongJianya(NationalLaboratoryforInfor

2、mationEngineeringinSurveying,MappingandRemoteSensing，,129LuoyuRoad,entofgeographicinformationscienceandtheoreandmoreneedsarerequiredtotheportantproblemthatscholarsfacuson.StartinZhansevaluationofasetof15shortestpathalgorithms,thispaperpresentsanefficientmethodofrealizetheshorte

3、stpathalgorithm.Resultshoethodperforms；inZhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ（graphgroimplementedatebuckets)以及DKD(theDijkstrasalgorithmimplementedin［dj,dk+lkj］式中，lkj是从点k到j的直接连接距离。　　3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。　　4)找到点i的前一点。从已标记的

4、点中找到直接连接到点i的点j*，作为前一点,设置：i=j*　　5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2)再继续。2　已有的Dijkstra算法的实现　　从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的2)～5)步。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些

5、要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据(如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系(由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关系)。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。　　网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表

6、示。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表［4］表示，其优缺点的比较见表1。表1　几种图的存储结构的比较Tab.1　TheparsionofSeveralGraphforStoringStructures名　称实现方法优　　点　　　　缺　　点　　　　　　　时间复杂度　　　　　　　　邻接矩阵二维数组1.易判断两点间的关系占用空间大O(n2+m*n)　　2.容易求得顶点的度　　邻接表链表1.节省空间1.不易判断两点间的关系O(n+m)或O(n*m)　　2.易得到顶点的出度2.不易得到顶点的入度　十字链表链表1.空

7、间要求较小结构较复杂同邻接表　　2.易求得顶点的出度和入度　　邻接多重表链表1.节省空间结构较复杂同邻接表　　2.易判断两点间的关系　　　　目前,对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法。TQQ、DKA以及DKD在这方面是比较典型的代表。TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程［1］。　　DKA和DKD是采用如图1所示的桶结构来支持这个运算，其算法的命名也来源于此。在DKA算法中，第i个桶内装有权值落在［b*i,(i+1)*b)范围内的可供

8、扫描的点，其中b是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护，这样每个点有可