最短路径迪杰斯特拉（Dijkstra）算法的优化

摘 要：Dijkstra算法是在道路网中选取最短路径，这是一个事先的选择过程，是理想的静止状态下的计算，所得的最短路径在现实中往往不会是最佳的路径。在车辆实际运行中，路况信息也就是道路权重值是随时动态变化的，这就要求能对最短路径进行重新的计算。针对Dijkstra算法存在的弊端，本文利用动态最短路径搜索方法进行了优化改进。

关键词：Dijkstra算法；最短路径；优化

1 Dijkstra算法分析

Dijkstra算法的计算是从路段长度的集合S中进行最短路径的对比选取，算法的速度与集合S的大小有直接的关系。城市的道路网中从V到Vi的最短路径为d（V，Vi），则d（V，Vi）中包含了所有满足d（V，r）< d（V，Vi）的顶点r，也就是集合S。在这个算法中，不仅仅计算了点V到Vi的最短路径，而且也计算得出了V到S集合中全部顶点的最短路径，这就产生了大量的无用顶点r，集合S越大则所需要计算的顶点r的数量越多，所占用的时间也就越多。如果城市的道路网比较大，两目的地之间的距离越远，在Dijkstra算法中所计算的顶点r甚至会遍布城市道路网中所有的顶点，这就增加了算法的额外运算量，降低了效率。

2 Dijkstra算法改进

现在的城市救援车辆基本上已经全部安装了GPS定位装置，可以实时的确定车辆的位置，这就为动态最短路径搜索方法的实现提供了设备上的支持。

动态最短路径搜索方法简单来说就是在车辆运行过程中，根据实时的车辆位置和路况信息进行最短路径的搜索，它的搜索范围仅局限在车辆所在位置周围一定的距离。在这种算法中虽然有固定的起点和目的地，但是在路径的选取中主要是根据车辆在道路上实际运行情况来确定每段道路的终点，也就是将起点与最终的目的地之间划分成一个个的短的区间，求解每个区间之间的最短路径。在车辆实际运行中经常会遇到两种情况：一种是车辆偏离预定路线比如走错路转错方向，无法按照预定的路线行驶；另一种是在车辆运行中路况发生变化如发生拥堵，在动态最短路径选择的方法下可以很好的解决此类问题。

动态最短路径搜索方法具有很大的灵活性和实用性，它的搜索范围仅在车辆周围所涉及的道路节点长度信息要比Dijkstra算法中少得多，因此计算所用的时间要短的多，而且所的到的最终路径可以认为是一条最佳的路径。

本文在动态最短路径选择方法下对Dijkstra算法进行了优化改进。

在该方法中首先要确定一个车辆道路通行时间的计算公式，本文采用如下公式进行计算：

（1）

式中：

--车辆在a路段的通行时间；

--a路段的长度；

--车辆平均车速；

α、β--道路参数；

--a路段的交通流量；

--单位时间内a路段最大通过车辆数。

改进后的计算方法步骤如下：

（1）将道路网数据进行划分

将起点V与目的地Vi之间的路段划分成n个区域，n的取值由两点之间的直线距离決定，距离越远n越大。划分成n个区域后，按照一定的范围将每个区域内的所有路段长度用集合Dn（li）分别存储。

（2）提取道路通行时间最短的路段

先在第一个路段区域内的路段长度集合D1（li）中，运用上述公式（1）计算得出每段路当前路况下的通行时间[ti]，将[ti]按照时间的长短进行序列排队，则通行时间最短的ta所代表的路段a就是最佳的路径选择。依次类推可以求的n个区域内的n条最佳路径。

（3）动态调节

车辆由上步确定的第一条最佳路径出发后，根据车辆GPS的实时定位信息和实际的车辆运行情况进行路径的动态调节。如果没有遇到影响通行时间的情况，车辆就按照既定的路线行驶。当车辆在道路行驶中遇到拥堵或偏移预定路线的情况时，将此时GPS定位的车辆位置点作为新的出发点，重复（1）操作重新进行区域划分，然后实施步骤（2），计算新的最佳路径，并反馈给道路上的车辆进行及时的调节。

（4）重复步骤（3）的操作，直到车辆到达目的地。

这种算法将路网信息进行了分区划分，并且只选取一定范围内的道路信息，这样就使的在计算过程中所要计算的数据量大大减少，调高了算法的效率。并且在该算法中是按照车辆实时前进方向的道路位置进行道路数据的选取，避免了对已通过路段信息的重复计算。Dijkstra算法的路径搜索范围可以看成是以起点和目的地之间距离为半径的圆形区域，而改进后的算法则可以看成是以起点和目的地为顶点的椭圆形区域如图1所示，由图可以很直观的看出改进后的算法要明显比原Dijkstra算法的数据搜索和处理量少很多。

图1 Dijkstra算法与改进算法搜索范围对比

3 小结

本文针对城市救援中的最短路径Dijkstra算法进行了分析，针对其弊端采用动态最短路径搜索的方法进行了改进，当然这种算法求得的最终路径长度并不是最短的，但它以道路通行时间最短为标准，是符合城市应急救援车辆要求的一种算法，这对救援最佳路线的选择具有重要的现实意义和应用价值。

参考文献

[1]刘根生，苏飞，赵娣.基于Dijkstra算法的两点间多目标最优路径问题建模和优化[J].池州师专学报.2007.21（3）：17-22.

[2]周玉清，张红梅.多源最短路径Floyd算法的分析与实现[C].第四届海峡两岸GIS发展研讨会暨中国GIS协会第十届年会，云南，2006.

作者简介：

王廷（1985.6--）男，汉族，山东泰安人，助教，硕士，主要从事工程测量教育教学研究。