一种基于改进型Dijkstra算法的路线规划方法研究

信息化研究

Informatization Research

Vol. 46 No. 2Apr. 2020

一种基于改进型Dijkstra算法的路线规划方法研究

梁波，杨新民

(中国电子科技集团公司第28研究所，南京，210007)

摘要：文章较为详细地介绍了路线规划的基本概念、数据需求、常用算法，并实现了一种基于二

叉堆结构的改进型Dijkstra算法，对其数据组织以及节点预操作进行了描述，对其空间复杂度和时间复 杂度进行了理论分析，同时通过试验进行证明。试验结果可以看出基于二叉堆结构的改进型Dijkstra 算法在数据量很大、稀疏度很高时，其计算速率明显优于传统Dijkstra算法。

关键词：路线规划；Dijkstra算法;二叉堆 中图分类号:TP301

〇引言

路线规划算法是图论中的核心问题之一，它 是许多更深层次算法的基础。同时，该问题有着 大量的生产实际背景。随着近年来经济的发展， 交通事业也正以前所未有的速度迅猛发展着。新 建道路和其他各种交通设施越来越多。对于出行 者来说，如何选择一个快捷、便利的出行路线尤为 重要。同样，在军事上，路线规划也有其重要的应 用价值。因此，研究路线规划算法有着重要的经 济和军事效益。

路线规划的方法有很多，根据自身优缺点，其适 用范围也各不相同。根据对各领域常用路线规划算 法的研究，按照各种算法发现先后时序及算法基本 原理，算法可大致分为4类:传统算法、图形学的方 法、智能仿生学算法和其他算法。传统的路线规划 算法有模拟退火算法、人工势场法、模糊逻辑算法、 禁忌搜索算法等。传统算法在解决实际问题时往往 存在着建模难的问题。图形学的方法则提供了建模 的基本方法，但是图形学的方法普遍存在着搜索能 力的不足，往往需要结合专门的搜索算法。图形学

的方法有C空间法、栅格法、自由空间法、Voronoi 图法等。处理复杂动态环境信息情况下的路线规划 问题时，来自于自然界的启示往往能起到很好的作 用。智能仿生学算法就是人们通过仿生学研究发现 的算法，常用的有蚁群算法、神经网络算法、粒子群 算法、遗传算法等。

1路线规划数据需求

地理信息系统的地理数据通常以文件或数据库 的形式进行存储，为了进行路线规划，需要导出“居 民地及附属设施”和“公路道路”这两个图层的数据。 图层数据按类型一般分为属性数据、几何数据和拓 扑数据。

对于“居民地及附属设施”图层，需要导出每个 地名的名称、行政区划、经纬度等信息。

对于公路而言，属性数据包括:路线编号、路线 名称、路段长度、路段宽度、路段等级(高速、国道、省 道、县乡道)等;桥梁的属性数据包括:桥梁编码、桥 梁名称、桥梁长度、桥梁宽度、桥梁净空高、桥梁载重 吨数等;隧道的属性数据包括:隧道编号、隧道名称、 隧道长度、隧道净空高等。几何数据即道路、桥梁、 隧道的组成坐标点。拓扑数据即道路、桥梁、隧道之 间的连接关系，根据拓扑数据形成拓扑关系图，以便 分析。

•

收稿日期：2019-12-22

13

•

•研究与设计•信息化研究2020年4月

有了这些数据，下面就可以根据相应的算法进 行路线规划。

域广泛，如电子游戏、GIS系统[7]、无线网广播 等领域。

算法的特点在于当选择下一个被探索

2路线规划算法

的节点时引人了已知的路网信息，特别是目标点 信息。通过对当前节点距终点的距离进行评估， 路线规划的基本思想是根据道路数据形成拓扑

图，然后根据过滤条件，求解图的最短路径。自 1959年Dijkstra提出最短路径搜索算法以来，很多 学者一直致力于最短路径搜索的研究[1]。2. 1

传统Dijkstra算法

传统Dijkstra算法用于计算一个节点到其他所 有节点的最短路径。主要特点是以起始点为中心向 外层扩展，直到扩展至终点为止[2]。Dijkstra算法 能得出最短路径的最优解，但由于它遍历计算的节 点很多，所以效率低[3]。对于顶点个数为〃、边的个 数为m的无向图来说，Dijkstra算法的时间复杂度 为O(Y)，空间取决于存储方式，邻接矩阵 为 〇(”2)。

对于边数少于V的稀疏图来说，可以用邻接表 来更有效地实现Dijkstra算法。同时可将二叉堆或 者Fibonacci堆用作优先队列来寻找最小的顶点。 当用到二叉堆的时候，算法所需的时间为0( (m + «)log m) ’Fibonacci堆會这将算法运行时间降到CKw + ??log n) 0

2.2 A*算法

如果有已知信息可用来估计某一点到目标点的 距离，则可改用A•算法，以减少最短路径的搜索 范围。

一般寻路算法，包含“盲目搜索”与“启发式搜 索”。“盲目搜索”主要包括纯随机搜索（Random

Generation and Search)、广度优先搜索（BFS)、深度

优先搜索(DFS)以及由它们衍生出来的一系列衍生 算法。“启发式搜索”主要包括局部择优搜索算法、 最好优先搜索算法。

盲目搜索只适用于求解比较简单的问题。而启 发式搜索则可用于较复杂的问题，其通过对搜索位 置的评估得到最好的位置，再由此位置继续搜索，直 到目标。这样可以省略大量无谓的搜索路径，提高效率。

A'算法属于最好优先搜索算法[4]，其应用领

• 14 •

作为该节点属于最优路径节点可能性的评价指 标，这样就可以优先搜索可能性较大的节点，从而 提高搜索效率。

与Dijkstra算法相比较，A•算法引入了当前 节点的估价函数，其可以定义为：

F(i) = G(f) + H(i) (1)

式中，G(0是从起点到当前节点的最短距离，可通 过Dijkstra算法获得；H(〇是从当前节点到终点最 短距离的评估价值，该部分的复杂度决定了 A•算 法的复杂度，一般为求高效取直线距离。

在算法中，最关键的信息为顶点和边，而顶 点的数量间接决定了边数的多少。由于算法的 空问复杂度为〇(m + n)，所以，若能有效地减少顶 点数，将大幅降低算法的空间消耗。A•算法的时间 复杂度为〇(/•/)，其中，/为评估函数的时间复杂 度；/为路径中的边数。所以，如果能有效地减少寻 路中需要判断的顶点数量，使边数下降，则算法的时 间消耗也会减少。2. 3 Boost Graph Library

Boost Graph Library 是一个 C++的模板库，提

供了邻接矩阵、邻接链表等图的数据组织以及

Dijkstra最短路径算法的实现，用于解决图论中的常

见问题[8]。

对于数据规模不大的图来说，可以直接利用

Boost Graph Library进行相关问题的求解。

3基于二叉堆结构的Dijkstra算法

3.1算法思想

二叉堆结构是一种数组对象，可以被视为一棵 完全二叉树。堆结构必须满足以下性质:对除了根 结点以外的每个节点有A[/wrenKz_)] < A[z_]或

Xf]，即某个节点的值不大于（或

不小于)其父节点的值。这样，堆中的最小(最大)元 素就存放在根结点中，且每一节点子树中的节点都

第46卷第2期梁波，等:一种基于改进型Dijkstm算法的路线规划方法研究

•研究与设计•

不小于(或不大于)该节点的值。

具有〃个元素的二叉堆是基于一棵完全二叉树 的，其高度为log

对于二叉堆的操作，其作用时

间至多与树的高度成正比，为〇(l〇gn)，因此，若采 用基于二叉堆实现的优先级队列来存储D^kstra算 法中所扩展处的D值（可能最短路径长度）及完成 对D值的松弛操作，则可大幅度降低算法的时间复 杂度，提高算法效率。3.2数据组织和数据存储

对于空间数据的组织，考虑到对于海量的空间 数据而言，用邻接矩阵存储图需要开辟》X «的存储 空间，对于一个大型稀疏图来说，计算效率和存储效 率都很低。所以可以采用邻接表来存储网络拓扑结 构以节省存储空间。邻接表是图的一种链式存储结 构，在邻接表中，节点元素保存在一个数组中。3.3节点排序和最短路径节点的选取

在Dijkstra算法中，网络图的每个节点均需实 现从未标记节点到最短路径节点的转变。这种转变 需要将大量的无序存储的未标记节点都扫描一遍， 从中选取一个最短路径节点作为中间节点。在数据 量大的情况下，必然会影响计算速度。解决此问题 的最有效的方法就是把这些要扫描的节点按标号值 进行排序，每循环一次就可取到符合条件的节点，这 样就可以大大提高算法的执行效率。

在改进算法中，初始时，待排序的节点以无序 形式连续存放在一个一维数组中，对其进行堆排 序，调整为堆后，各节点即是以完全二叉树的顺序 存储结构形式存储，〇号单元存放的即是调整后的 堆顶元素，后面依次以左子数、右子树。在调整堆 的过程中时间复杂度为〇(l〇g«) ( «为待排序节点 个数）。与从无序结构下的数组或链表中选择下 一个最短路径节点比较，明显节约了时间，提高了 算法执行效率。3.4空间复杂度分析

对于数据的存储，传统Dijkstra算法采用图论 中的邻接矩阵方法，其存储量为《 X n («为网络图 中的节点数)。通常的网络图尽管节点很多，但与节 点相关的节点数目并不多，一般都为稀疏图，这样该 存储方法将浪费大量的空间，而且在计算时亦要花

费大量的时间遍历无意义的数据。而改进算法采用 了邻接表的链式存储结构，对于一个无向图来说，其 存储量为〇(m + 2w) ( m为节点列表中同节点关联 的所有弧段数目）。另外还使用了两个数组，其中一 个数组D[V]用来存储所求得源点到其他所有节点 的最短路径值，另外一个数组7TV]用来暂存待排 序的节点。所以总的空间复杂度为〇(所+ 4«)。与 传统Dijkstra算法相比较，节省了空间，提高了存储 效率。

3.5时间复杂度分析

传统Dijkstra算法采用广度优先的搜索策略， 在访问了网络中所有的节点后，最终生成从源点到 其余各点的最短路径树。该算法在选择最短路径节 点时需要访问所有的未标记节点，效率低下，整个算 法的运行时间为〇(«X»)。而改进型Dijkstm算法 主要步骤在查找待排序的节点和堆排序上，因待排 序节点为所有已标记节点的邻居节点的并集与标记 集合的差集，所以这个步骤的运行时间主要取决于 已标记节点的邻接点集合元素数量的多少（而该数 量值往往小于未标记集合中的元素个数），查找次数 最多为w次。在排序过程中，每次调整的时间复杂 度不会超过满二叉树的高度l〇g(«)。这两个过程 共需迭代执行n次，因此整个算法理论上最长运行 时间仅为〇(n(log« + m))。当网络拓扑结构图具 有的节点树〃较大且其关联矩阵为一个稀疏矩阵 时，相对传统Dijkstra算法，优化算法大大减少了计 算次数与比较次数，在一定程度上提高了运行速度。 3. 6

基于二项堆结构的Dijkstra算法

二项堆是由一组二项树构成的数据结构。对于 插人、删除、抽取最小关键字等基本操作，一般的二 叉堆都能以较高的效率完成。当涉及两个堆的合并 等操作时，二项堆的优势显示出来了，它能将〇(«) 的时间降低到O(logn)。3. 7

基于Fibonacci堆结构的Dijkstra算法

Fibonacci堆是一种松散的二项堆[9]，与二项堆

的主要区别在于构成Fibonacci堆的树可以不是二 项树，并且这些树的根排列是无序的。Fibonaca堆 的优势在于它对建堆、插人、抽取最小关键字、联合等操作能在0(1)的时间内完成。这是对二项堆效

• 15 •

•研究与设计•信息化研究2020年4月

率的巨大改善。但由于Fibonacci堆的参数因子以 及程序设计上的复杂度，使得它不如通常的二叉堆 合适。

规划问题，取得了较好的效果。今后，还可以采用二 项堆结构和Fibonacci堆结构来实现Dijkstra算法， 并通过比较，选择合适的算法来解决实际路线规划 问题。

参考文献

4试验验证及分析

在CPU为Pentium双核2. 6 G，内存为2 G的

计算机上，通过比较传统Dijkstm算法和二叉堆结 构Dijkstra算法，求解不同规模的路线规划问题的 时间，试验结果如表1所示。

表1试验结果

试验规模

顶点数=1 〇〇〇,边数=500顶点数=10 〇〇〇,边数=5 000顶点数=1〇〇 〇〇〇,边数=50 000顶点数=1 〇〇〇 〇〇〇,边数= 500 000

[1] 陈玉敏，龚健雅，史文中.多级道路网的最优路径算法研究

[J].武汉大学学报(信息科学版），2006,31(1): 70 - 73.

[2] 吴海峰.最短路径算法_ Dijkstra及Floyd算法[J].中国新

通信，2019(2) :32-33.

[3] 李健.基于Dijkstra最短路径算法的优化研究[JQ.渭南师

范学院学报，2009,24(5) :63 - 66.

Dijkstra(s)

156297

传统二叉堆结构

Dijkstra(s)

121123

[4] 朱云虹，袁一.基于改进A-算法的最优路径搜索[J].计算

机技术与发展,2018,28(4) =55-59.

[5] 曹栋，王瑞，曹越.基于A•算法的无人机攻击编队航迹规

划[J].沈阳航空航天大学学报，2016,33(4) :61 - 65.

[6] 来耀，荆明娥.基于A•算法优化的片上网络源路由算法 [J].复旦学报（自然科学版），2018,57(5):605- 610.[7] 熊伟，张仁平，刘奇韬，等.A-算法及其在地理信息系统中

的应用[J].计算机系统应用，2007,16(4) :14_ 17.

从试验结果可以看出，对于稀疏结构的图，采用

二叉堆实现的Dijkstra算法的计算时间优于传统

[8] Siek J, Lee L Q, Lumsdaine A. The boost graph library user guide and rerference manual[M], Addison-wesley,2005.[9] 李鹏，张远平，李丽.Fibonacci堆及其在外存储算法中的应

用[J].计算机工程与设计，2011,32(8):2745 - 2747.

Dijkstra算法，尤其是数据量很大、稀疏度很高的

时候。

5结束语

利用二叉堆来实现Dijkstra算法，从理论分析

梁波（1983—

)，男，高级工程师，主要研究方向为

和试验结果来看，时间复杂度和空间复杂度都有较 大的改进。在某项目的研制中使用该算法求解路线

指挥信息系统总体设计。

Study on a Path Planning Method Based on the Improved Dijkstra Algorithm

Liang Bo, Yang Xinmin

(The 28th Research Institute of China Electronics Technology Group Corporation, Nanjing, 210007，China)

Abstract:This paper introduces the basic concepts of route planning, data requirement and the commonly

used algorithms in detail. It realizes a kind of improved Dijkstra algorithm which is based on binary heap struc­ture. Its data organization and node pre-operation are described and the space complexity and time complexity are analyzed in theory. Meanwhile, experiment is taken for verifying the proposed method. The result shows that under the condition of a large amount of data or high sparse degree, the improved Dijkstra algorithm based on the structure of binary heap is superior to traditional Dijkstra algorithm in calculation speed.

Key words：route planning; Dijkstra algorithm; binary heap

欢迎投稿:xinxi@vip. I63. com

• 16 •

|