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

Dijkstra最短路径算法的一种高效率实现* 摘要在已存在的一些最短路径算法测试总结的基础上， 根据GIS中网络计算的实际情况，从网络结构的拓扑表示以 及Dijkstra算法中快速搜索技术的实现入手，提出了一种 Dijkstra最短路径算法的高效率实现方法。 关键词最短路径算法；网络分析；地理信息系统 分类号 P208； 022 An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm Yue Yang Gong Jianya National Laboratory for Ination Engineering in Surveying, Mapping and Remote Sensing, WTUSM, 12Luoyu Road, Wuhan, China,30079 Abstract With the development of geographic ination science and the wide use of GIS software, more and more needs are required to the network analyses. As the key of network analyses, computing the shortest paths over a network is an important problem that scholars focus on. Start with the data structure during its computation process and combined with Zhan s uation of a set of 1 shortest path algorithms, this paper presents an efficient of realize the shortest path algorithm which is based on Dijkstra algorithm. Result shows that this pers well in practice. Key words shortest path algorithm； network analysis； GIS 随着计算机的普及以及地理信息科学的发展，GIS因 其强大的功能得到日益广泛和深入的应用。网络分析作为 GIS最主要的功能之一，在电子导航、交通旅游、城市规划 以及电力、通讯等各种管网、管线的布局设计中发挥了重要 的作用，而网络分析中最基本最关键的问题是最短路径问 题。最短路径不仅仅指一般地理意义上的距离最短，还可以 引申到其他的度量，如时间、费用、线路容量等。相应地， 最短路径问题就成为最快路径问题、最低费用问题等。由于 最短路径问题在实际中常用于汽车导航系统以及各种应急 系统等，这些系统一般要求计算出到出事地点的最佳路线的 时间应该在1 s〜s内，在行车过程中还需要实时计算出车辆 前方的行驶路线，这就决定了最短路径问题的实现应该是高 效率的。其实，无论是距离最短、时间最快还是费用最低，它 们的核心算法都是最短路径算法。经典的最短路径算法 Dijkstra算法是目前多数系统解决最短路径问题采用的 理论基础，只是不同系统对Dijkstra算法采用了不同的实现 方法。 据统计，目前提出的此类最短路径的算法大约有17 种。Zhan等人对其中的15种进行了测试，结果显示有3种 效果比较好，它们分别是TQQ、DKA the Dijkstra5s algorithm implemented with approximate buckets以及 DKD the Dijkstra s algorithm implemented with double buckets , 这些 算法的具体内容可以参见文献［1］。其中TQQ算法的基础 是图增长理论，较适合于计算单源点到其他所有点间的最短 距离；后两种算法则是基于Dijkstra的算法，更适合于计算 两点间的最短路径问题［1］。总体来说，这些算法采用的数 据结构及其实现方法由于受到当时计算机硬件发展水平的 限制，将空间存储问题放到了一个很重要的位置，以牺牲适 当的时间效率来换取空间节省。目前，空间存储问题已不是 要考虑的主要问题，因此有必要对已有的算法重新进行考虑 并进行改进，可以用空间换时间来提高最短路径算法的效 率。 1经典Dijkstra算法的主要思想 Dijkstra算法的基本思路是假设每个点都有一对标号 dj, pj,其中dj是从起源点s到点j的最短路径的长度从 顶点到其本身的最短路径是零路没有弧的路，其长度等于 零；pj则是从s到j的最短路径中j点的前一点。求解从起 源点s到点j的最短路径算法的基本过程如下 1 初始化。起源点设置为①ds0, ps为空;②所有 其他点dioo, pi;D标记起源点s,记ks,其他所有点设为 未标记的。 2）检验从所有已标记的点k到其直接连接的未标记的 点j的距离，并设置 djmin [dj, dklkj] 式中，lkj是从点k到j的直接连接距离。 3）选取下一个点。从所有未标记的结点中，选取dj中 最小的一个i dimin [dj,所有未标记的点j] 点i就被选为最短路径中的一点，并设为已标记的。 4）找到点i的前一点。从已标记的点中找到直接连接 到点i的点j*,作为前一点,设置 ij* 5）标记点io如果所有点已标记，则算法完全推出， 否则，记1＜门，转到2）再继续。 2已有的Dijkstra算法的实现 从上面可以看出，在按标记法实现Dijkstra算法的过 程中，核心步骤就是从未标记的点中选择一个权值最小的弧 段，即上面所述算法的2）〜5）步。这是一个循环比较的过程, 如果不采用任何技巧，未标记点将以无序的形式存放在一个 链表或数组中。那么要选择一个权值最小的弧段就必须把所 有的点都扫描一遍，在大数据量的情况下，这无疑是一个制 约计算速度的瓶颈。要解决这个问题，最有效的做法就是将 这些要扫描的点按其所在边的权值进行顺序排列，这样每循 环一次即可取到符合条件的点，可大大提高算法的执行效 率。另外，GIS中的数据如道路、管网、线路等要进行最 短路径的计算，就必须首先将其按结点和边的关系抽象为图 的结构，这在GIS中称为构建网络的拓扑关系由于这里的 计算与面无关，所以拓扑关系中只记录了线与结点的关系而 无线与面的关系，是不完备的拓扑关系。如果用一个矩阵来 表示这个网络，不但所需空间巨大，而且效率会很低。下面 主要就如何用一个简洁高效的结构表示网的拓扑关系以及 快速搜索技术的实现进行讨论。 网络在数学和计算机领域中被抽象为图，所以其基础 是图的存储表示。一般而言，无向图可以用邻接矩阵和邻接 多重表来表示，而有向图则可以用邻接表