改进的Dijkstra最短路径算法在GIS-T中的研究与实现

戴文博 殷招伟 钱俊彦

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

改进的Dijkstra最短路径算法在GIS-T中的研究与实现

戴文博 殷招伟 钱俊彦

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

Dijkstra最短路径算法广泛应用于交通运输和网络优化等领域，但是在实际应用的过程中仍存在一些不足。文章针对道路拥挤、交叉路口等待和单行道限行等方面提出了一种改进的基于时间最短的最短路径算法。传统的最短路径算法中图的顶点是抽象的，不含权重的，改进的算法中图的顶点是有权值的，用来表示道路交叉口的等待时间。通过编程实现该算法，实验结果表明，道路拥挤、交叉口等待和单行道限行对交通路径选择有很大影响。因此，改进的算法求得的最短时间路径更加符合实际，具有一定的应用价值。

Dijkstra最短路径算法；最短时间路径；交通运输；网络优化

随着城市化进程的加快，城市交通网络的规模也在不断扩大，交通设施日益发达，但这也使城市交通变得异常复杂。这也就促使了交通地理信息系统（GIS-T，Geographic Information System for Transportation）的应用日益广泛。GIS-T是地理信息系统（GIS）[1]在勘测设计、道路规划和管理等领域中的具体应用，它充分考虑了现有的交通网络的特征，过滤掉 GIS多余的功能，减少冗余，更加高效、快捷的管理和规划交通[2]。为了能够使得资源和时间得以充分利用，必须考虑到车辆路径规划。车辆路径规划问题一般指的是对一系列的起点和终点，调用一定的车辆，组织选择一条或多条适当的行车路线，使车辆有序的通过它们，在满足指定的约束条件下（如距离最短、时间最短、费用最低等），争取实现如车辆行驶里程最短、运行时间最短、运费最低等目标[3]。而 GIS-T的重点之一就是路径规划分析，因此，交通路径规划问题必然成为 GIS-T的研究热点之一，而路径的选择取决于多种因素，较常见的有三种：车辆行驶距离、车辆所需费用和车辆行驶时间。在具体应用中，有些司机愿意选择距离最短，有些司机愿意选择费用最少，有些司机愿意选择最短出行时间。

无论采用何种标准，最优路径规划最终都可以归结为在特定道路网中寻找具有最小代价的最短路径问题[4]。

因此，就需要合理的规划交通路线以满足人们需求。本文就如何使得行驶时间最短进行了讨论。

在研究问题的过程中，可以将实际的交通网络模型化成网络图，根据图论的相关知识，交通网络中的两点之间的最短路径就可以用图中顶点之间的最短路径表示。图的最短路径问题由很多国内外学者进行了深入的研究，提出了许多种最短路径算法，其中Dijkstra提出了一个按路径长度递增的次序产生的最短路径算法是目前已知的理论上最完善、应用最多的算法[5]。这些算法解决了两点之间的最短路径问题，但是有时需要的并不是两点之间的最短距离而是追求时间和速度上的需求。那么我们就需要考虑将图中的边或弧的权值由行驶时间替换路段距离，对于道路拥挤和交叉路口红绿灯等待时间也是需要考虑的因素，而对于某些单向限行的道路可能在一些地图软件中搜索到的最短路径是不太实用的。

1 相关基础知识

1.1 Dijkstra最短路径算法

Dijkstra最短路径算法是由荷兰计算机科学教授迪杰斯特（E.W.Dijkstra）在1959年提出的，它被公认为是最经典的算法之一，也是解决最短路径问题的基础算法。它可以从某点到网络中其余各顶点的路径长度依次递增的顺序产生最短路径，适应于所有弧或边的权值为非负的图。

Dijkstra算法的基本思想可以简单的描述为：从起始顶点出发，找到从起始顶点到其余各顶点中第1、第2……第n短的路径，这样就获得了从起始顶点到其余各顶点的最短路径。如果要获得从起始顶点到某个顶点的最短距离，则直到找到这个顶点的最短路径就停止，不再继续查找[6]。

1.2 算法理论基础

单源最短路径问题，即根据最短路径的最优子结构性质，在图中求出从给定的顶点到其他任意顶点的最短路径。最优子结构的性质可以描述为：如果D(i, j)= {Vi…Vk…Vs…Vj}是从顶点i到j的最短路径，k和s分别是这条最短路径上的中间结点，那么D(k,s)必定是从顶点k到顶点s的最短路径距离[7]，下面证明该性质的正确性。

假设D(i, j)={Vi…Vk…Vs…Vj}是从顶点i到j的最短路径，D(k, s)不是从k到s的最短路径距离。那么则有D(i, j) =D(i, k)+D(k, s)+D(s, j)，而D(k, s)不是最短的，故存在另一条从k 到s比D(k, s)更短的D’(k, s),那么D’(i, j)=D(i, k) +D’(k, s)+D(s, j) ,由于D’(k, s)＜ D(k, s),那么D’(i, j)＜ D(i, j)，这与D(i, j)是从i到j的最短距离相矛盾，从而该性质得证。

根据以上性质可知，如果在一条从 i到 j的最短路径{Vi…Vk，Vj}，那么{Vi…Vk，Vj}，Vk是Vj的前驱结点，那么{Vi…Vk}也必然是从i到k的最短路径，据此，Dijkstra提出的一个按路径长度递增的次序产生的最短路径算法，如对于起点V0，首先选择与其直接相连的顶点中长度最短的顶点Vi，那么可得V0到Vj的最短距离Distance[j]= min{Distance[j] , Distance[j]+matrix[i][j]}[8]。

翻转课堂教学可以解决上述问题，以学为本建设优质的在线开放课程，开启课程资源共享与应用模式，学生课下先学习老师提供的基础知识，如果有问题就可以记录下来，在课堂上由老师答疑或同学讨论来解决。翻转课堂通过把传统的课堂学习和线上学习的优势结合在一起，实现线上线下混合式教学，可以更好地加强面对面的互动，培养学生团结协作的能力，提高教学效果，开启学生深度学习，满足不同学生对象的学习需求[5]。

2 最短时间路径算法

2.1 道路网的模型建立

对于前面提到道路拥堵而导致的时延，我们可以通过交通部门发布的实时数据来获取该道路的实时平均速度，从而根据路长，求得该段线路的车辆行驶时间。将交通网络转换为网络图，那么该段路线车辆行驶时间即为网络图中两顶点的弧的权值；对于交叉口红绿灯延误的时间，可以转换为图中顶点的权值，而在传统的最短路径算法中，图的顶点是没有权重的，只起到标识的作用，在算法中是不起作用的；对于单行线路段，可以动态的改变有向图中弧的方向。由此，可以得到该道路网的模型如图1。

图1 道路网模型图

图1中，圆圈分别表示各个道路网的顶点，圆圈旁的Vi （i=0，1，…，5）为各顶点的标识符，圆圈中的数字表示各个交叉口的等待时间，弧段上的数字表示车辆路段行驶时间，当图中某两个顶点分别表示起点和终点，延误时间不需计入。

2.2 改进的算法思想

由于在传统的最短路径算法中，图的顶点是没有权值的，因此，我们需要在定义图的结构过程中额外增加一个vertex[MaxVexNum]数组来存储图中所有顶点的权值来解决交叉口等待时间[9]。然后根据上面的性质假设存在G=＜V,E＞，源顶点V0，Distance[i]记录的是V0到Vi最短时间，path[i]记录的是V0到Vi前驱的一条最短路径，matrix是用来表示带权有向图的邻接矩阵，matrix[i][j]表示弧＜Vi, Vj＞上的权值。若＜Vi, Vj＞不存在，则将matrix[i][j]置为∞或者一个相对较大的值。求解V0到其余各顶点的最短时间路径，由于在改进的算法中，图的顶点是有权重的，因此，在计算源点到各顶点的最短时间时需要将图的顶点计算进去。基本思想如下：

（1）初始化顶点集S={V0}和T=V-S，集合S中存放已经找到的最短时间路径的顶点而集合T中存放余下的顶点。

（2）不断的从集合T中选择顶点V0到顶点Vu的最短时间路径长度即Distance[u]最小的顶点Vu加入到集合S中。

（3）更新V0到集合T中剩下的顶点的最短时间路径长度，Distance[j]=min{Distance[j],Distance[j]+matrix[i] [j]+vertex[i]},这是本算法的核心部分。

（4）重复上面的(2)、(3)两步骤，直到S=V结束。

2.3 算法求解过程针对图1，算法的求解过程如下表1所示，V0到各个顶点的最短时间路径分别是：V0-＞V2，最短时间为10；V0-＞V4，最短时间为30；V0-＞V2-＞V3，最短时间为80；V0-＞V2-＞V3-＞V5，最短时间为95。

表1 V0到各个终点的Distance值和最短路径求解过程

2.4 算法部分代码

在传统的最短路径算法中，图顶点没有权重，因此，顶点在算法中不起作用，但是在改进的算法中，图的顶点是有权重的，因此，在图结构定义的时候，添加一个 vertex[Max Vexnum]数组来表示顶点的权重。

3 实验结果与分析

3.1 实验结果

本文的仿真实验环境：处理器为Inter(R) Core(TM)2 Duo CPU/2.93GHz,内存为2.00GB的PC机，根据上述算法，编写的程序代码在VS2010集成环境下运行结果图2和图3。

3.2 实验结果分析

本文是用车辆行驶的时间来替换路段长度表示路径上的权重，由此还是转换为求解网络最优路线问题。由表1和图3，可以算法的求解过程和程序执行过程是一致的。由图2和图3可知，在传统的算法中，V0到V3的最短路径为V0-＞V4-＞V3，计算权值为50，V0到V5的最短路径为V0-＞V4-＞V3-＞V5，计算权值为60；而在改进的算法中，V0到V3的最短路径为V0-＞V2-＞V3，计算权值为 80，V0到 V5的最短路径为V0-＞V2-＞V3-＞V5，计算权值为95。这就充分说明了图中顶点有无权值，对最短路径有较大的影响，即交叉口的交通红路灯等待时间对最短时间路径的选择有很大的影响，对于单行线，只是改变有向图中的弧的方向，那么只需在搜索最短时间路径前更新邻接矩阵matrix[i][j]中对应的值。因此改进的算法更贴近实际。而对于算法执行的时间，由于结点个数少，两个算法的执行时间都在纳秒级别。改进后的算法时间复杂度O(n2)与传统最短路径算法的复杂度一致。

图2 传统最短路径算法的执行结果

图3 改进的算法的执行结果

4 结语

本文主要讨论了Dijkstra最短路径算法并在其基础上提出了基于时间的最短时间路径算法，传统的算法网络图中顶点是没有权重的，而改进的算法增加了顶点的权重来表示交叉口红绿灯等待时间，该算法主要解决了道路拥挤、交叉路口红绿灯等待和单行线路段限制的路径规划问题，并通过算法编程实验证明，使得搜索到的最短时间的路径更加的符合实际，更能满足人们的需求，具有较大的应用价值。

[1] 刘学军,徐鹏.交通地理信息系统[M].北京:科学出版社, 2006.

[2] Miller H J, Shaw S L. Geographic information systems for transportation: principles and applications[M]. Oxford University Press,2001.

[3] 孙丽君,胡祥培,王铮.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,(11):31-37.

[4] 林清岩.智能交通中车辆最优路径规划策略研究[D]. 吉林大学,2013.

[5] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997.

[6] Chuan-xiang REN,Xin-gang HAO,Ying-rui Wang. Research on the Optimization and Simulation of the Shortest PathBased on Algorithm of Dijkstra[J]. Journal of Measurement Science and Instrumentation, 2010.

[7] 胡运权.运筹学教程(第 3版)[M].北京:清华大学出版社,2007.

[8] 秦锋,汤亚玲.数据结构:C语言版[M].北京:清华大学出版社,2011.

[9] 陈悦.基于行程时间组合预测模型的动态路径诱导系统研究[D].华南理工大学,2012.

Research and implementation of the improved Dijkstra shortest path algorithm in GIS-T

Dijkstra shortest path algorithm(DSPA) is widely used in fields of communication and transportation and network optimization, etc. But there are still some shortcomings in the process of practical application. We propose an improved SPA based on the minimum duration which is directing at the aspects such as congested roads, the intersection waiting and one-way street restrictions. The vertex of diagram in tradition SPA is abstract and does not contain the weight, while does and is used to represent the intersections waiting time in improved algorithm.We program to implement it and the results show that the above three aspects mentioned has a great influence on choice of the transportation route. Therefore, the shortest time path wh3ich is gained by the improved algorithm is more in line with the actual and the improved algorithm has a certain application value.

Dijkstra shortest path algorithm; the shortest time path; communication and transportation; network optimization

TP312

A

1008-1151(2015)02-0001-03

2015-01-12

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