改进的Dijkstra算法

1、湖北文理学院毕 业 论 文 （设 计）论文（设计）题目： Dijkstra算法在嵌入式GIS中的改进与研究 学 院 继续教育学院 专 业 计算机应用技术 层 次 专 科 学 生 周金涛 指导教师 2016年5月20日- II -Dijkstra算法在嵌入式GIS中的改进与研究专业：计算机应用技术 学号：201421255 姓名：周金涛 指导教师：摘要：Dijkstra算法是求解嵌入式GIS系统中最短路径的经典算法，通过对Dijkstra算法进行分析，改变图的存储结构和搜索方法，采用基于矩形限制区域的二叉排序树改进算法，减少了内存存储空间，缩短了查询时间，在一定程度上优化了最短路径的计算过程，实

2、际数据测试也表明了该算法的有效性。关键词：Dijkstra算法；嵌入式GIS；最短路径；矩形限制区域；二叉排序树Research and Improvement of Dijkstra Algorithm to Embedded GIS SystemAbstract: Dijkstra algorithm is a classic algorithm to solve the shortest path in the embedded GIS system. Changing the storage structure of the graphics and the search method

3、, Dijkstra algorithm is modified by using binary sort tree based on rectangle boundary area through analyzing algorithm. The memory space needed is decreased and the search time is shortened and the algorithm has optimized calculation process in some degree. The algorithm is achieved good results by

4、 testing some data. Key Words: Dijkstra algorithm; embedded GIS; shortest path; rectangle boundary area; binary sort tree目 录一、引言1二、Dijkstra算法及其存在的问题1三、基于Dijkstra算法的GIS路径优化2（一）改进的方面2（二）网络路径优化的拓扑结构3（三）限制搜索区域加载部分网络模型4（四）Dijkstra算法的优化改进5四、算法分析及测试7五、总结8参考文献9一、引言随着无线网络的普及和智能移动设备的发展，嵌入式移动终端成为空间信息服务的核心组成和数字

5、城市的重要服务方式。最短路径分析是GIS中最主要的一个基本功能，其中Dijkstra算法1由于算法稳定，适应网络拓扑，成为最短路径规划中的一个经典算法。但由于Dijkstra算法是一种以起点为中心，想外层层搜索的盲目搜索算法，随着网络规模的扩大，对于嵌入式GIS无论是计算时间还是存储空间上的需求都是十分巨大的，必须进行优化。许多基于Dijkstra的最短路径分析算法对此进行了改进。TQQ算法、DKA算法、DKD算法2以及最大相关边法3、最大邻接点法4减少了算法对存储空间的需求，基于二叉堆优先级队列算法、四叉堆优先级队列的算法5以及排序优化算法6则提高了算法的运行效率。这些算法或是节省了存储空间

6、但导致系统的响应速度变慢，或是搜索时间变短但占用大量的存储资源，无法在嵌入式GIS系统中正常运行。直线优化Dijkstra算法7和快速Dijkstra优化算法8对算法本身和存储结构都进行了优化，但前者不太适合城市间道路的交通复杂情况，而且搜索过程中需要进行大量空间距离计算，而后者使用的村树结构十字链表过于复杂。因此，笔者试图对Dijkstra算法进行数据结构和运算方法的优化处理，并将其应用于GIS路径分析，希望能够同时提高时间与空间效率。二、Dijkstra算法及其存在的问题经典Dijkstra算法将网络节点分成3部分：未标记结点、临时标记结点和永久标记结点。网络中所有结点首先初始化为未标记结

7、点，在搜索过程中与最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有结点都成为永久标记结点，算法结束。设G=(V, E)是一个赋权有向图，对于图中的每一条边都有权值w。单源的最短路径问题是指求一源结点到其他所有结点的最短路径及路径长度。算法中把V分成两个子集S和T，S集合用来存放已经得到的最短路径的结点，集合T满足T=VS，用来存放目前还没有参与计算的结点。设长度为N的一位数组DistN，用来存放从源点到图中其他结点的最短路径长度。设二维数组path_matrix，该矩阵用来记录源点到图中其他每个结点的

8、最短路径所经过的结点的集合，可以根据该矩阵进行路径回溯。Dijkstra算法的流程如下：（1） 初始化集合S和集合T；（2） 利用图的邻接矩阵来初始化DistN数组；（3） 初始化path_matrix，使其中元素都为无穷大；（4） 从DistN中选择最小的元素，假设此最小元素对应结点的索引为i，即结点i；（5） 将结点i加入到集合S中，同时从集合T中删除结点i；（6） 根据结点i来更新距离数组DistN，只更新源点到集合T中的结点之间的距离，更新过程如下：if( Distj > Disti + path_matrixij )Distj = Disti + path_matrixij;（

9、7） 如果集合T不为空，则返回（3）；如果集合T为空，则结束算法。Dijkstra算法简单直观，容易编码实现，已经证明能够计算出最短路径的最优解，有非常强的鲁棒性，但它的计算效率是一个很大的问题。首先它采用带权的邻接矩阵存储图形数据，占用大量存储空间；而且它是一种盲目搜索算法，对于具有n个结点的图，计算源点到图中所有其余结点的最短路径的算法时间复杂度为O(n2)，对于一座大中型城市，无论是计算时间还是存储空间上的开销都是十分巨大的。算法的搜索速度受图的存储结构的影响：搜索速度快，则图的存储空间就小；反之，图的存储空间大，则会降低搜索速度。所以经典的Dijkstra算法不适合CPU处理能力较低、

10、存储空间较小的嵌入式GIS，必须对其进行优化。三、基于Dijkstra算法的GIS路径优化（一）改进的方面本文在改进时间与空间效率方面进行了以下重要改进：（1） 采用了一种新型的网络存储模型；（2） 采用矩形限制区域，结合方向优化，分块加载地图数据，限制搜索区域；（3） 采用二叉排序树优化搜索临时结点。（二）网络路径优化的拓扑结构传统的Dijkstra算法在存储图形数据和运算时，采用n×n的邻接矩阵，其中n为网络模型的结点数。但是当网络模型的节点数较大时，将占用大量的计算机内存。而且在网络的节点数很大而各结点的邻接结点数又不多的情况下，有大量的无效的0元素或元素，造成了空间的浪费。在

11、此基础上进行矩阵运算，必将浪费大量运行时间。为了避免空间的浪费，本文的优化Dijkstra算法拟采用邻接结点的结构。该结构通过构造邻接矩阵和判断矩阵以实现拓扑数据的存储。邻接矩阵用来存储结点之间的邻接关系，判断矩阵用来存储邻接矩阵中对应弧的权值。这样只需要2×n×m的存储空间，m为最大邻接结点数，城市道路的相邻一般不超过5个，所以占用空间为2×n×5。（1） 构造邻接矩阵。以结点为行，邻接的结点为列，矩阵的行数为网络模型的实际结点数，列数为网络模型的最大相邻结点数。邻接矩阵的行按结点的索引号从小到大顺序排列，与结点i邻接的结点号写在矩阵的第i行，如果结点

12、i的邻接结点数小于最大邻接结点数，则用0填充，直至填满矩阵；（2） 构造判断矩阵。对照邻接矩阵，用邻接矩阵里的各个元素的邻接关系对应的弧的权值填在矩阵的同一个位置上，就得到了相应的判断矩阵；针对图1所示的网络模型，邻接矩阵和判断矩阵如图2所示。这种存储结构既节省了存储空间，也提高了运算速度。图1 网络模型实例 （a）邻接矩阵 （b）判断矩阵 图2 邻接矩阵和判断矩阵实例（三）限制搜索区域加载部分网络模型对于嵌入式系统，考虑硬件计算环境的限制，不需要一次性加载所有的网络模型信息。本文采用的矩阵限制区域地图数据选择法9，以用户输入的起点和重点为地图数据选择的参考点，在参考点的基础上，按照一定的规则

13、扩大范围以生成最初的矩形区域。GIS两点之间除空间距离关系之外，还有方向的关系，理想状态下，两点之间线段最短，这条线段作为一条道路存在的可能性极小，但这条从起点至终点的线段代表了一个路线的趋势方向，顺着这个趋势方向的某条路径是起点到终点的最短路径的组成部分的可能性极大。因此在实际搜索过程中，可以借助备选结点到目标点的趋势方向来确定最佳。在矩形限制区域内遍历道路图层，求最短路径的道路的范围选择原则如下：（1） 载入用户设置的起点、终点、途经点、障碍点，以起点和终点作为矩形区域对角线上的两个顶点，确定范围，加载范围以内的数据，可以减少空间分析时所要检索的临时结点的数量；（2） 以A为起点，B为终点

14、。设Pi为与A点的邻接点，求线段PjA与线段AB的夹角。如果夹角小于90°，把Pi选入范围；否则继续计算下一个A点的邻接点Pi+1；（3） 以B为起点，A为终点。设Qj为B点的邻接点，求线段QjB与线段AB的夹角。如果夹角小于90°，则把Qj选入范围；否则继续计算下一个B点的邻接点Qj+1；（4） 以所有选入范围的A点的邻接点P为起点，B为终点，进行类似（2）中的计算；同时以所有选入范围的B点的邻接点Q为起点，A为终点，进行类似（3）中的计算；（5） 对（4）中计算完成之后，再进行更深一层的计算，直到两个集合相交，就确定了算法所涉及的道路的范围子集；（6） 在道路范围自己中

15、应用Dijkstra算法，来求A点到所有其他结点的距离，到前点为B时，算法结束，并根据path_matrix矩阵回溯路径，输出路径和最短距离；（7） 如果在限制范围内没有找到一条最优的路径，则适当扩大范围，并采用分块加载数据的方法。采用矩形限制区域地图数据选择法并借助方向优化，可以有效缩小搜索范围，使得搜索结点的数量明显小于全部结点数，提高了搜索的速度。（四）Dijkstra算法的优化改进在经典Dijkstra算法中，临时标记结点无序地存储在无序表中，这无疑成为Dijkstra算法的瓶颈。因为每次在临时标记结点中搜索路径最短的结点时，都要遍历所有的临时标记结点。解决办法就是将临时标记结点按照最

16、短路径排序，每个搜索过程不必全部遍历或者较少地遍历临时标记结点。为了减少最短路径分析过程中搜索的临时结点数量，尽快到达目标结点，优化Dijkstra算法利用二叉排序树，减少更新T集合的时间。二叉排序树是利用二叉树的结构特点来实现对元素排序的。二叉排序树的构造过程实质上就是排序的过程，它以二叉排序树作为媒介，将一个任意的数据序列编程一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。二叉排序树构造的思路为：以待排序的数据的第一个数据为根节点；对以后的各个数据，逐个插入结点；插入过程服从规定“在每次插入时，原有树结点位置不变，只是将新数据的结点作为一个叶结点插入到合适的位置，使二

17、叉树中任何结点的数据与其左右子树结点数据之间的关系仍然符合二叉排序树”。为了将二叉排序树结构应用于Dijkstra算法，主要是以起点到选择的结点距离作为关键字，建立二叉排序树。每次从二叉排序树的最左下的叶结点取得最小值结点，将该结点加入集合S中，并从二叉排序树中删除该结点。之后以该节点为永久标记结点，计算该结点到T集合中各个结点的距离，如果该距离小于关键字，则将原来的结点删除，更新关键字。二叉排序树中的结点的具体数据结构为：struct Nodelong nodeID; /结点索引号long distance; /源点到该节点的距离，作为关键字struct node *left_child,

18、*right_child; /结点的左右子结点struct node *parent; /结点的父结点综合上述三个方面的改进，得到了基于矩形限制区域的二叉排序树改进Dijkstra算法，流程如图3所示。图3 基于矩形限制区域的二叉排序树改进Dijkstra算法流程图四、算法分析及测试本文对地图数据采取分块加载的策略，使用矩形限制区域并借助趋势方向优化，见笑了搜索的范围和结点的数目。改进的Dijkstra算法使得最短路径搜索过程不再盲目，而是在方向上趋向终点。改进算法的时间复杂度主要耗费在生成二叉排序树以及在二叉排序树上插入结点。从空树出发，通过将n个结点逐个查找并插入，可生成一个二叉排序树，每

19、个结点插入的时间复杂度平均为O(lbn)，生成二叉树的时间复杂度则为O(nlbn)，所以总的时间复杂度为O(nlbn)，比起经典Dijkstra算法的O(n2)要降低不少；另外，采取邻接结点存储法使得空间复杂度由原来的O(n2)降低到O(n)。因此，从理论上来说，算法的优化取得了良好的效果。本文采用以下嵌入式系统环境对改进算法进行了测试：操作系统为Windows CE，CPU为Intel 2.0 GHz，运行内存为1GB，开发工具为Visual Studio，编程语言为C#。实现了对北京市地图Dijkstra算法最短路径求取的仿真实验，证明该算法计算最短路径是高效且具有较强鲁棒性的。如图4所示

20、是将给予矩形限制区域的二叉排序树改进Dijkstra算法应用于北京市地图查询系统中的一个应用实例（小于1000条弧段，查询道路时间<1/5s），图中紫色的线段表示生成的最短路径。图5显示的是该算法的效率。图4 基于改进Dijkstra的GIS路径分析算法结果示例图图5 改进Dijkstra算法的效率比较五、总结本文首先阐述了经典Dijkstra算法的原理及缺陷，并在此基础上，提出了改进的最短路径算法基于矩形限制区域的二叉排序树改进Dijkstra算法。该算法使用邻接结点结构，节省了内存，可以应用于结点数巨大的网络模型。采用矩形限制区域地图数据选择法并借助趋势方向优化，可以有效地缩小搜索范围，减少了搜索结点的数目。使用二叉排序树对最短路径分析过程中搜索的临时结点进行排序，减少了临时结点的数量，加快了搜索进程。与传统Dijkstra算法相比，改进算法有效地降低了算法的时间复杂度和空间复杂度。下一步有待研究的问题是需要更加周密地分