Dijkstra最短路径算法改进研究及应用

1、Dijkstra最短路径算法改进研究及应用赵 雍（陕西省交通规划设计研究院，陕西 西安 710068）摘 要 Dijkstra算法是求解最短路径问题的经典算法。但是，在开发交通地理信息系统时，公路线形矢量图中，可能存在大量的折线段，以及大量的端点，如果直接利用此算法构造端点之间的邻接矩阵，要耗费大量宝贵的计算时间和存储空间，从而使其在实际应用中，对求解复杂路线图形的最短路径显得非常困难。针对在实际应用中存在的问题，本文提出了对传统的Dijkstra最短路径算法改进的新方法，即对复杂的公路网数据进行预处理，生成路网拓扑结构数据文件，并结合Dijkstra算法按路径长度递增次序产生最短路径的思想，

2、来解决实际公路网复杂线状图形的最短路径问题。最后，利用VC+语言工具，将这种方法在1:20 万陕西省交通地理信息系统中进行实现，证明此方法是准确和高效的。关键词 地理信息系统；Dijkstra算法；最短路径；公路网；拓扑关系Improvement Research on Dijkstra Shortest Path Algorithm andIts ApplicationZhao Yong（Shaanxi Provincial Transport Planning Design and Research Institute, Shaanxi Xian 710068）Abstract：The D

3、ijkstra algorithm is one of a classical algorithms which to solves the shortest path problem. However, in practice, when we design a special Geographic Information System for Transportation, there are possibly a large number of poly lines and vertexes in the road linear vector graphics. If we direct

4、ly make use of this conventional algorithm, we must make the adjacent matrix between one vertex and the other. And it will consume much computing time and storage space, so it is very difficult to be used in the practical project. Therefore, in allusion to the above questions, this paper puts forwar

5、d an improved method. The contents are as follows: On the one hand, we need to preprocess those complex and unreasonable road network data, and then make a road network topology data file. On the other hand, we combine the topology data file with the Dijkstra algorithm idea that the shortest path is

6、 created according to the increasing order of path length. At last, according to this improved method we develop the GIS software1:200,000 scales Shaanxi Provincial Geographic Information System for Transportation by using VC+ programming language to make a simulation analysis testing .The result in

7、dicates that the method is accurate and highly effective.Keywords：Geographic Information System; Dijkstra algorithm; shortest path; road network; topology1 引言最近几年来，国内外学者对交通地理信息系统进行了大量的研究，其中最短路径分析是交通地理信息系统网络分析的一个基本问题，常规算法分为两种：解决单源点最短路径问题的Dijkstra算法和解决所有结点间最短路径问题的Floyd算法6。其中Dijkstra算法是目前理论最完善的非负权值网络最短

8、路径算法，它以极强的抗差性而得到广泛应用，并且已成为国内外大型GIS平台网络分析模块的首选算法7。但是在现实情况下，公路线形矢量图中可能存在大量的折线段，以及大量的端点，直接利用上述算法构造端点之间的邻接矩阵，要耗费大量宝贵的计算时间和存储空间，从而给实际求解最短路径问题带来一定的困难。针对上述存在的问题，本文提出对传统Dijkstra算法的实现进行改进，来求解在现实情况下基于复杂公路线形矢量图形的最短路径问题。改进方法具体分为两部分：首先把原始的线性矢量图形进行先期处理，生成线段拓扑结构数据文件，将结点信息映射到线段的端点上；接下来再根据传统的Dijkstra算法思想，利用线段拓扑数据文件，

9、求解最短路径。此方法在开发出的1:20万陕西省交通地理信息系统中进行应用，证明是准确和高效的。2 Dijkstra算法思想从图结构中某个源点找出到其余各顶点的最短路径，E.W.Dijkstra提出了按路径长度递增次序产生最短路径的算法思想8。即若按长度递增的次序声称源点到其它顶点的最短路径，则正在生成的最短路径上除终点外，其余顶点的最短路径均已生成。算法的具体思路如下6：假设网络G（V , E）,V为网络中所有结点的集合，E为网络中所有边的集合，s为起始结点，S为已计算出最短距离的结点集合，则V-S就是最短距离待求解的结点集合。 初始化初始时，只有起始结点s的最短距离是已知的。 计算未知点的最

10、短路径从当前V-S中选择最短距离的结点来扩充S，以保证算法按路径长度递增次序产生顶点的最短路径。根据这种思想，当前最短距离最小的未知结点k的最短路径是：s,已知结点1，已知结点2，已知结点n，未知结点k则距离为：s到已知结点n的最短距离+<已知结点n，未知结点k>边长。 重复。仅当V-S中所有结点的最短距离为或为空时，s到所有结点的最短路径求解完毕。 Dijkstra算法是一种基于贪心策略的最短路径算法，它要求在路径选择中的每一步所选择的路径都是目前为止最好的，在局部最优而导致总体最优的假设下寻求最佳路径。不同的实现方法构成了Dijkstra算法的庞大家族，如：采用快速排序的FIF

11、O队列的Dijkstra算法3；采用最大邻接节点数构造邻接节点矩阵的Dijkstra算法4；采用改进型OPEN CLOSE表的Dijkstra算法5等。1996年，Zhan和Noon使用实际交通网络测试了Cherkassky总结的17种最短路径算法，测试结果表明：由于公路交通网络不存在负权边，所以Dijkstra算法更适合求解交通网络最短路径12。在Dijkstra算法中，临时标记结点集被作为无序表进行处理。那么要选择一个加权距离最小的结点就必须把所有的结点都扫描一遍。原本求解的是起点和终点之间的最短路径，而求出的则是从起点到其余各点的最短路径，在大数据量的情况下，这无疑是一个制约计算速度的瓶

12、颈。在实际应用中，面对庞大的路网，传统的Dijkstra算法求解出的其余最短路径都是不必要的，我们只需要从起点到终点的那条最短路径。因而寻求一种存储量较小，且具有较高时效性（要求算法必须在一定的时间内完成）的最短路算法是非常必要的。本文通过探索，设计出了一种更加精致的数据结构，并对搜索算法进行改进，来最大幅度的提高最短路径算法在实际应用中的运行效率。3 Dijkstra算法实现的改进传统Dijkstra算法在实现时需要构造端点之间的邻接矩阵或邻接表，当端点数量较少时，应用此算法实现的应用系统占用的内存空间可以接受，但实际情况下，公路网中的结点数量会相当庞大，如果网中的结点数为n，则算法要求的内

13、存量为2nn结点内存。一般情况下，公路网中的结点分为端点（连接一条或者两条线段的点）和交叉点（连接三条或者三条线段以上的点）两种。根据统计，在1:20万的陕西省交通图中原始公路线段（高速公路，国、省、县、乡道，专用公路）1983条，公路网的结点数达到36815个，当进行最短路经分析时，构造邻接矩阵所需的内存空间至少为2900,000,000结点内存，如果结点数量更为庞大时，可能内存空间会出现不足，进而影响应用程序运行效率。因此，需要对此算法的实现进行改进，即根据E.W.Dijkstra提出的按路径长度递增次序产生最短路径的思想，提出一种新方法来解决在实际应用中存在的问题。此方法的整个工作流程如

14、图1所示。其实现需解决以下两个关键问题：如何正确提取和构建网络拓扑结构；如何高效进行最短路径分析。下面将对这两个问题进行研究，得出相应的解决方案。图1 Dijkstra算法改进的工作流程3.1 原始数据预处理，构建路段的拓扑结构数据文件对公路网进行最短路径分析，首先必须将现实中的公路网实体抽象化为图论中的网络图，然后通过图论中的网络分析理论来求解公路网最短路径问题。在实际应用中，公路网的表现形式一般为数字化的矢量图。为了能够高效地进行最短路径分析，改进的方法需要首先对原始公路图进行预处理，建立其相应的网络拓扑关系。预处理的工作主要包括:对原始公路线段进行交叉打断处理，生成线线不相交叉的公路网;

15、对打断后的路段创建拓扑关系；生成具有拓扑关系的路网数据文件。原始公路线段交叉打断后，形成了互不交叉路段，其数据结构如图2所示：图2 路段对象的数据结构路段类ZTrafficLine 由实体类ZTrafficEntity派生而来，ZTrafficEntity类对象存储空间坐标串，交叉结点隐含在坐标串的端点上；ZTrafficLine的SLinks存储所有与此路段的一个端点连接的所有路段集合，ELinks为另一个端点连接的所有路段集合，Weight为此路段的权重，为计算累计最小权重服务。此数据结构是Dijkstra算法思想（即按路径长度递增次序产生最短路径）实现的基础。路段交叉打断完毕后，生成路网

16、拓扑结构数据文件，其文件格式如表1所示。每一条公路由多个路段组成，每个路段存储与其连接路段的ID，在最短路径分析时，可方便、快捷的索引路段，进行最短路径计算。表1 路网拓扑结构的文件格式3.2 改进的Dijkstra算法实现图3 标记最短路径的流程原始数据预处理，生成路段拓扑结构数据文件后，将此文件载入用户应用程序，路网的拓扑关系被保存在每一条路段内，在进行最短路径分析时，不必为建立结点的邻接矩阵或邻接表而耗费大量的内存空间。改进的方法分为两部分：标记最短路径和回溯生成最短路径。其中标记最短路径是Dijkstra算法实现改进的核心，流程框图如图3所示。求解最短路径的实现步骤如下：（1）输入路径

17、分析起终点，搜索距离起终点最近的路段作为起止路段。（2）初始化所有路段的累积权值（m_pathWeight） 为0，前驱指针（m_prev）为-1，标记起始路段的前驱指针为空。清空最短路径结果集。（3）通过路段端点所包含拓扑连接信息，搜索路段，结果保证从初始路段到此路段的累积权值最小，并标记其前驱指针。（4）重复（3）。仅当搜索到终止路段时，最短路径标记完毕。（5）从终止路段开始回溯，搜索路段的前驱指针，将其保存到最短路径结果集，仅当前驱指针为空（即搜索到起始路段），最短路径求解结束。在改进方法中，空间复杂度和网中所加载边的数目成正比，空间复杂度为O（e）。 4 改进方法的应用本文采用VC+进

18、行实现，数据采用1:20万陕西省公路网数据，原始数据为AutoCAD的DXF格式。数据预处理时首先进行DXF格式解析，然后对公路网进行交叉打断处理，生成实体数据文件和路段拓扑数据文件（注：在交叉打断之前还需要进行区域打断和比例分段，由于和本文讨论问题无关，且篇幅所限，故不提供详细论述），发布的用户应用程序在开始运行时加载实体数据文件和路段拓扑结构数据文件。应用系统除实现任意结点间最短路径的查询显示外，还实现了：地图的放大、缩小、漫游功能，信息查询，亮显和打印等功能。用户可以在图中任意选择起点和终点，然后进行最短路径查询，就得到了从起点到终点的最短路线所经过的路段集，并高亮显示最短路径（图4）。

19、因在此之前，程序已经加载了网络的拓扑信息，则不需要最短路径分析前的数据准备阶段，故可进行快速的最短路径查询。起点 路径列表属图4 改进方法在交通地理信息系统中的应用 多次的运行结果证明，无论是运行速度还是准确程度上，都取得了很好的效果。还需要说明的是，本软件不依赖特定的线性矢量图形，其功能可不加修改地应用到其他的线性矢量图形，具有通用性。5 结论本文针对现实的公路网特点，提出了一种实用、高效的最短路径分析解决方案。其中，重点解决了公路网矢量图拓扑结构的提取和构建、高效最短路径算法的实现等关键技术，由于路网的拓扑结构在数据预处理时生成，并隐含到用户应用程序的路段结构中，因此利用此方法，克服了在实

20、际进行最短路径分析时构造邻接矩阵或邻接表的局限性，提高了最短路径分析的响应速度和实现效率。该方法在1:20万陕西省交通地理信息系统中成功应用，并得到以下结论：（1）对Dijkstra算法实现的改进可适合任何复杂管网模型的最短路径分析，增加了程序的实用性和灵活性。（2）在实现上，不依赖特定的线性矢量图形，具有通用性。对不同的网络矢量图形数据经过预处理，生成网络拓扑关系数据文件，在以后的每次最短路径搜索中可快速的进行分析操作。（3）算法和程序的实现过程中并没有局限于一种属性图形，因而可进一步扩充为不相同线性矢量属性的最优查询。参考文献：1 Cherkassky, B. V., Goldberg, A. V., and Radzik, T. Shortest