Dijkstra算法在GIS车辆诱导系统的优化实现

殷招伟 戴文博 钱俊彦

（桂林电子科技大学计算机科学与工程学院，广西 桂林 541004）

Dijkstra算法在GIS车辆诱导系统的优化实现

殷招伟 戴文博 钱俊彦

（桂林电子科技大学计算机科学与工程学院，广西 桂林 541004）

为了满足人们日益增长的出行需求，跨学科的智能交通系统应运而生。最短路径分析是GIS车辆诱导系统应用的关键问题，Dijkstra算法是解决该问题的常用算法。文章结合二树Dijkstra算法的思想和现代多核多线程的技术，对Dijkstra算法进行了优化与改进，并对该算法在车辆诱导系统中的应用进行了探讨。该系统以桂林市为例模拟了最短路径搜过程，证明该算法的高效性和实用性。

最短路径；Dijkstra算法；车辆诱导系统

车辆诱导系统作为智能交通系统的子系统，在交通管理上发挥着重要作用。地理信息系统 GIS(Geographical Information System)以其强大功能应用在电子地图应用在车辆诱导系统中[1]，其核心问题是求解最短路径问题。最短路径问题是指在一定的评判准则下，寻找源点到目标节点之间的最优路径[1]。

用于解决最短路径问题的算法被称作“最短路径算法”[2]，包括传统Dijkstra算法、A*算法和各种限制搜索区域算法。最常用且最典型的为Dijkstra算法，由于该算法是一种穷尽遍历算法，必定会找到最短路径，但对于节点数目巨大的交通网络，其搜索效率很低。本文对该算法进行优化和改进，利用该优化算法可以快速找到最优路径。最终将其应用于车辆诱导系统中，为人们出行提供便利，并证明该算法的实用性。

1 Dijkstra算法

荷兰计算机学科教授迪杰斯特（E.W.Dijkstra）于1959年提出了Dijkstra算法。该算法被公认为是最经典的算法之一，也是解决最短路径问题的基础算法。它可以描述为从某点到网络中其余定点的路径长度依次递增的最短路经树，换言之Dijkstra算法是用于计算网络中起始节点s到其他所有可达节点的最短路径树。在实际求解最短路径过程中，一旦发现路径树中已经存在目标节点t，则终止算法。其中，最短路径起始节点s到目标节点t的路径就是最短路径。Dijkstra算法将网络中节点分为三类：未标记节点、候选节点和永久节点。算法初始化时把所有节点初始化为未标记节点，找到与起始节点有最短路径的节点称作是永久节点，在路搜索过程中与永久节点相连的节点标记为候选节点。算法可以描述为在循环搜索，在候选节点集合中查找出距离源节点 s最近的节点，同时将该节点标记为永久节点，直至把目标节点或者所有节点标成永久节点为止。其算法描述如下：

上述算法过程描述中，有向图G可以用[N,A]来表示，其中N为所有节点集合，A表示所有边的集合。边(i,j)∈A的权值用lij表示。假设存在最短路径节点s到节点t，并且所有边(i,j)满足 lij≥0。FS(u)表示节点 u所有后继节点(u,j)∈A的集合，u∈N；BS(v)表示节点v所有前驱节点的集合，(i,v)∈A，v∈N。标签集合du用来表示路径树T中根节点到各个节点路径长度；pu表示路径树 T中的上级节点；Q表示候选节点集合。

2 Dijkstra算法优化与改进

Dijkstra算法是一种穷尽遍历算法，其核心思想是遍历完所有的节点，找到根节点到目标节点之间所有的可达路径并从中选出最短路径。因此，在搜索过程中即使一开始找到最短路径也要继续遍历完其他所有节点，结果会消耗不必要的内存资源，降低搜索效率。因此在实际当中，需要优化搜索方方式，其主要分为两种：一是加快搜索速度；另外就是减少搜索节点数目。本文从减少搜索节点数目这个方面优化Dijkstra算法。

2.1 二树Dijkstra算法

二树Dijkstra算法最早由Dantzig在文献[3]中提出，但是他并未给出算法结束的条件。Pohl在文献[4]补充该算法为双向搜索算法，形成了较为完善的二树Dijkstra算法。

二树Dijkstra算法基本思想就是构造两棵分别以起点为根和以终点为根最短路径搜索树，它们拥有相同的节点。然后分别以这两棵路径搜索树沿着相反的方向开始搜索，同时在当前的上级节点中保存的是前驱节点而不是后继节点。其中，两棵树是以交替的形式增长，故该算法又称串行二树Dijkstra算法，当两棵树中出现相同节点时结束算法。这个相同节点称作公共节点。但需要注意的是，两棵树中出现公共节点并不是得到最短路径的必要条件，即找到的公共节点不一定在最短路径上。该算法所需的存储空间是Dijkstra算法的两倍，算法流程如下：

2.2 二树Dijkstra算法的改进

二树Dijkstra算法中，我们可以看到两棵路径搜索树是相互独立的，唯一关联的是需要检测两棵树中是否存在公共节点。在多核多线程技术中，关联并不会造成任何的干扰[5]。因此，通过为两棵路径树创建两个线程来扩张节点，就实现了并行的二树Dijkstra算法。当其中一个线程检测到公共节点时，则通知另一个线程同时结束算法，算法流程如下图所示。

相比串行二树Dijkstra算法，并行二树Dijkstra算法在搜索过程中是从两个方向同时进行搜索，因此其搜索效率是串行二树Dijkstra算法的两倍。但在实际编码实现过程要考虑到线程之间的同步与互斥，即对临界资源的加锁与解锁。因此实际的并行二树 Dijkstra算法的效率达不到串行二树Dijkstra算法的两倍，但其实际搜索效率仍然高于串行二树Dijkstra算法。其搜索范示意图如图1所示。

图1 算法搜索范围示意图

2.3 测试结果与分析

将本文中提出的上述三种算法应用到路网分析中，因为路网中节点数目较多，故其数据结构采用邻接表存储。测试数据来源DIMACS网站提供的美国道路网信息，测试结果如表2所示，其中的T表示消耗时间，单位为妙，W表示搜索路径的权值。

表2 算法结果统计表

从表中可以得到，在搜索过程中消耗的时间关系是：Dijkstra算法＞二树Dijkstra算法＞并行二树Dijkstra算法。在准确性方面，Dijkstra算法求解出来的一定是最短路径，尽管二树Dijkstra算法和并行二树Dijkstra算法的不能保证其结果一定是最短路径，但是非常接近Dijkstra算法的结果。在大量实验的基础上，并行二树Dijkstra算法的算法结果准确率在90%以上，基本满足人们的出行要求。

3 并行二树 Dijkstra算法在 VRGS中的应用

因为城市路网中节点数目巨大，故在改进算法中采用邻接表作为存储结构，在保证道路完整性的前提下大幅减低了空间复杂度[6]。最终将本文提出的改进算法—二树 Dijkstra算法应用到车辆诱导系统中。

3.1 算法设计实现

建立道路网络拓扑结构。定义一个Node类，用来表示点要素，由唯一编号(ID)、前驱弧段（PreEdges）和后继弧段（AdjEdges）三个属性组成。PreEdges和AdjEdges都是集合，分别记录了该节点的所有前驱弧段和后继弧段。弧段用Edge类来表示，记录了弧段连接的节点和弧段的一些基本属性信息。整个网络拓扑图用 Graph类表示，一个关键的属性是节点集合属性，记录所有的节点，并以哈希的方式存储。然后创建两个工作线程分别从起点和终点开始搜索。定义一个永久标签集合作为两个线程的公共变量，当其中一个线程向其添加永久节点时检测该集合中是否存在该节点，如存在即为公共节点，结束算法；反之添加。

3.2 算法运行结果分析

传统Dijkstra算法和并行二树Dijkstra算法的执行结果如图3和图4所示所示。六合路口和象山公园两个位置的ID分别为1116和382。图中红色路线为六合路口到象山公园的最短路径，蓝色的点表示算法执行过程中搜索过的结点，其节点数量反应邻接节点的搜索规模。

图3 传统Dijkstra求解最短路径结果图

图4 并行二树Dijkstra求解最短路径结果图

实验中统计的结果表明，并行二树Dijkstra算法搜索的结点数为498，相比传统Dijkstra算法搜索的735结点，减少将近32%。由于并行的不可预测性，其执行结果不是确定的，所以实验过程中搜索的节点数也在变化，但大部分情况下其搜索的节点总数相对要少很多。

4 结束语

本文提出并行二树Dijkstra算法可以有效的解决最短路径问题，在车辆诱导系统中的应用证明了该算法的实用性。但是这种优化算法是一种以空间换取时间的算法，因为构造了两棵路径搜索树，所以会产生一定的附加数据，因此下一步的工作应当考虑如何进一步优化数据结构，减少冗余数据。

[1] 姜凤辉,李树军,姜凤娇,等.基于GIS的Dijkstra改进算法及其在交通导航系统中的应用[J].测绘与空间地理信息,2011,(4):129-131.

[2] 王树西,吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学,2012,(5):223-228.

[3] Dantzig G B. On the shortest route through a network[J]. Management Science,1960,6(2): 187-190.

[4] Nicholson T. Finding the Shortest Route Between Two Points in a Network[J].The Computer Journal,1966, 9(3):275-280.

[5] 黄国睿,张平,魏广博.多核处理器的关键技术及其发展趋势[J].计算机工程与设计,2009,30(10):2414-2418.

[6] 王海梅.基于GIS的最优路径算法研究与实现[D].南京理工大学博士学位论文,2008:7.

Efficient implementation of Dijkstra algorithm in vehicle route guidance system based on GIS

The interdisciplinary application of intelligent transportation system comes into being just to meet people’s growing demand.The analysis of shortest path is the key problem in the application of VRGS (Vehicle Route Guidance System), the Dijkstra algorithm is the common algorithm to solve this problem effectively. Combined two-tree Dijkstra algorithm and multi-core and multi-threading technology, this paper optimizes and improves the traditional Dijkstra algorithm. And it discusses the application of the algorithm in VRGS．At last, this paper poves its practicality and efficiency by simulating the shortest path search process of Guilin.

shortest path ;Dijkstra shortest path algorithm; vehicle route guidance system

U49

A

1008-1151(2015)02-0025-04

2015-01-12

殷招伟，桂林电子科技大学计算机科学与工程学院硕士，研究方向为 GIS-T应用；戴文博，桂林电子科技大学计算机科学与工程学院硕士；钱俊彦，桂林电子科技大学计算机科学与工程学院博士。