Dijkstra算法的改进及其在车辆导航系统中的应用

郭春桦

摘 要：本文分别阐述传统Dijkstra算法和改进Dijkstra算法的算法思想，并在仿真实验中比较这两个算法在实际应用中的效果，用具体数据证明改进Dijkstra算法能更好的解决当前交通拥堵问题。

关键词：Dijkstra算法；最短路径；最优路径；带权图；车辆导航

1 引言

随着我国经济的快速发展，很多家庭都拥有汽车，私家车数量的剧增，使得交通路况恶化，交通拥堵现象越来越严重。这给居民的出行带来了极大的不便，严重影响了我们的工作生活。为了解决交通拥堵的问题，各相关部门采取了很多措施，增派交警到关键路段指挥，车辆限行政策，甚至是增加道路基础设施建设，但这些措施要么收效甚微，要么成本昂贵。这种情况下，各国纷纷致力于新兴交通科技的研究，以应对目前严峻的交通环境。车辆导航系统就是其中最重要的一项技术，它通过向驾驶员提供到达目的地的最优路径来引导驾驶员行驶，缩短车辆在道路上的停留时间，进而减少拥堵，改善交通情况。

2 最优路径的内涵

对于车辆导航的研究，为驾驶者选择一条最好的路径是关键。人们刚开始关注的是基于已有道路基础的从当前位置到目标地点路程最短的路径，这种路径是静态不变。但在现实应用中，由于交通情况是不断变化的，两点间路程最短并不表示出行时间最短，当最短路径拥堵时，路程长的路径可能反倒耗时短。因此最优路径必须将实时交通流的分布状况和其他因素加入到考虑分析中，选择行驶时间最短的路径，更能满足实际的需要，这种时间最短的路径，是基于实时交通信息的、是动态的。

3 Dijkstra算法求路程最短路径

Dijkstra算法是目前求解最短路径问题的理论上最完备、应用最广泛的经典算法，它可以求出带权图中指定顶点到图中其他所有顶点的最短路径。其基本思想是按路径长度递增的次序产生最短路径：

把图中所有顶点V分成两组：

⑴S：已求出最短路径的顶点的集合

⑵T=V-S：尚未确定最短路径的顶点集合

依据起点v到T中顶点vk的最短路径，要么是从v到vk的直接路径的权值，要么是从v经S中顶点到vk的路径权值之和，将T中顶点按最短路径递增的次序加入到S中。

那么，现在只要把交通路网抽象成一个带权图，就可以利用Dijkstra算法確定两地间的最短路径，具体规定如下：

⑴顶点：道路的交叉口或端点

⑵弧：两顶点之间的路段（含有方向）

⑶弧的权：路段长度

⑷路段上的任一地点依靠其最近的顶点。

4 改进Dijkstra算法求基于实时交通信息的时间最短路径——最优路径

4.1 影响行驶时间的因素有哪些

⑴拥堵情况；

⑵红绿灯的延误时间；

4.2 把影响因素按照一定标准进行量化

对于拥堵情况，我国公布的《城市交通管理评价指标体系》中规定，用城市路上机动车的平均行驶速度来描述起交通拥堵程度：⑴畅通：不低于30km/h；⑵轻度拥挤：20～30km/h；⑶拥挤：10～20km/h；⑷严重拥挤：低于10km/h。这样就能根据路段长度和平均行驶速度计算得到该路段的行驶时间。对于红绿灯，直接把延误时间作为度量标准。这些实时数据，可以通过各种交通服务设施获得，如环形线圈检测器等。

4.3 将城市路网抽象，建立相关网络模型

⑴顶点V：道路交叉口或端点

⑵顶点的权Wv：红绿灯延误时间

⑶弧R：两顶点间的路段

⑷弧的权Wr：路段需要的行驶时间

⑸路段上的任一地点依靠其最近的顶点。

传统的Dijkstra算法中，顶点是不含权重的，但我们确定最短时间路径时，交叉口的时间延误必须考虑在内，所以顶点是有权值的。

4.4 在上述网络模型中求时间最短路径的算法

根据以上分析，为了求时间最短路径，改进的Dijkstra算法描述如下：

⑴假设用带权邻接矩阵arcs表示带权有向图，arcs[i][j]表示弧的权，若弧不存在，则权值为∞；用向量W表示顶点的权，W[i]表示顶点vi的权值；S表示已求出最短路径的顶点的集合，初态为空；V-S表示尚未确定最短路径的顶点集合，初态为全部顶点；向量D，它的每个分量D[i]表示从始点v到每个终点vi的最短路径的长度，初态为：

⑵取vj，使得

vj就是当前求得的一条从v出发的最短路径的终点，令

⑶修改从v出发到集合V-S上任一顶点vk可达的最短路径长度，如果

则修改D[k]为

⑷重复操作（2）（3），直到求出到指定顶点的最短路径。

⑸仿真实验

下面以一个模拟路网为例，说明路程行驶时间和最优路径求解方法。

图1表示按传统方法抽象的交通路网，这里，弧上的权表示路程（单位km），为了简化示意图，直线表示双行线，箭头表示单行线。

取得实时交通信息之后，计算出每段路程所需的行驶时间，并添加红绿灯延误时间，得到新的带权有向图（图2），其中，弧上的权表示所需行驶时间，顶点中的权表示红绿灯延误时间，单位分钟。

1）假设始点是v，目标地点是v5，传统Dijkstra算法执行过程：

求出v到达v5的路程最短路径为v—v3—v2—v5，路程长度为12km。

2）改进Dijkstra算法算法执行过程：

求出v到达v5的行驶时间最短路径为v—v1—v5，所需行驶时间为15分钟，而传统Dijkstra算法求出的路径在相同的交通情况中需要时间31分钟，实验数据表明，改进的Dijkstra算法求得的路径虽然路程比较远（21km），但由于只要经过一个红绿灯，延误时间少，而且，路况良好，车流比较顺畅，所以所需行驶时间比传统Dijkstra算法求得的路径少了许多，这种方案更能满足用户的实际需要，而且引导驾驶者避免拥挤的路段，选择车流相对顺畅的路段，更能解决交通拥堵的问题。

[参考文献]

[1]贺正兵，关伟.考虑信号交叉口影响的分散路径诱导策略[J].北京工业大学学报，2013（10）.

[2]严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.1996.

[3]王一松.基于实时交通信息的最优路径规划算法研究[J].计算机与现代化，2013（2）.

[4]卫玮.基于实时交通信息的最优路径算法研究与实现[D].长安大学.2009.

[5]翟振，孙鑫，李志锋.基于Dijkstra算法的车辆导航系统路线优化技术[J].测绘科学.2008（S1）.

[6]李妍峰.基于实时交通信息的城市动态网络车辆路径优化问题[J].系统工程理论与实践.2013（7）.

[7]田明星.路径规划在车辆导航系统中的应用研究[D].北京交通大学. 2009.

[8]李进燕.基于简化路网模型的行程时间预测及导航算法研究[D].重庆大学.2012.