论文导读：Dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。Dijkstra算法的基本思想是以源点为圆心，按最短路径长度递增的顺序通过对路径长度迭代得到从源点到其他各目标结点的最短路径。所以需要进行优化。
关键词：最短路径，Dijkstra算法，优化
最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值和最小的路径，是一类受到普遍重视和研究的网络优化问题，广泛应用于计算机科学、交通工程、通信工程、运筹学等众多领域。实际生活中的许多问题都可归结为最短路径问题。邮政自动分拣机、计算机网络结点上的路由选择、人工智能游戏设计、交通咨询系统等都是最短路径问题的现实应用。由于带权图中权值所代表的意义不同，最短路径也不仅仅局限于地理意义上的距离最短，还可以引申为最少费用、最短时间、延时最短、吞吐量最大等[4]。
Dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。发表论文。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。Dijkstra算法的基本思想是以源点为圆心，按最短路径长度递增的顺序通过对路径长度迭代得到从源点到其他各目标结点的最短路径。
1 Dijkstra算法原理
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算非负权值图中一个结点到其他所有结点的最短路径，是一个非常经典的贪心算法例子。发表论文。基本思想是：把带权图中所有结点分成两组，第1组包括已确定最短路径的结点，第2组为未确定最短路径的结点。按最短路径长度递增的顺序逐个把第2组的结点加入第1组中，直到从源点出发可到达的所有结点都包含在第1组中[2]。
2 Dijkstra算法描述
根据Dijkstra算法的基本思想，引入如下状态变量：
1）辅助向量D，可用数组实现，其每一个分量D[i]用来存放源点到其他结点的最短路径长度；
2）集合V和S，其中V集合用来存放未确定最短路径的结点，S集合用来存放已确定最短路径的结点。S的初始状态为空集，V则包含带权图中的所有结点。
3）辅助变量path_matrix，可用二维数组实现，用来记录源点到其他各个结点的最短路径所经过的顶点。
由于Dijkstra算法是按照最短路径长度递增的顺序逐个确定源点到各个结点的最短路径的，所以源点到各结点的最短路径或者是源点到此结点的弧，或者是中间只经过已确定了最短路径的顶点（即S集合中的结点）而最终到达此结点的路径。
根据以上分析，得到如下的算法描述[1]：
1）初始化集合V、S，同时利用带权图的邻接矩阵arcs初始化数组D，即若源点到相应结点有弧，对应的分量取值为弧上的权值，否则对应的分量取值为∞；
2）选择D中最小的数组分量，假设为D[i]，则i就是已求得源点到其最短路径的终点，故将S=S∪{i},即将已确定最短路径的结点i加入S集合；
3）根据结点i修改更新数组D中源点到集合V-S中的结点k所对应的分量，即若D[i]+arcs[i][k]<D[k]，则D[k]=D[i]+arcs[i][k]；
4）重复2）、3）操作，直至所有的结点确定最短路径，即集合V为空。
对下图G施行Dijkstra算法，假设源点V1，求解V1到其他各个结点的最短路径。
图G
假设源点为v1，则第一个选择的顶点是v1，路径长是0，D[]={0，50，10，∞，16}；
Step1 S={v1}，V={v2，v3，v4，v5}，S点集扩充，v3为下一个最短路径顶点，路径长为10，D[]={0，50，10，25，16}；
Step2 S={v1，v3}，V={v2，v4，v5}，S点集扩充，v5为下一个最短路径顶点，路径长为16，D[]={0，50，10，21，16}；
Step3 S={v1，v3，v5}，V={v2，v4}，S点集扩充，v4为下一个最短路径顶点，路径长为21，D[]={0，41，10，21，16}；
Step4 S={v1，v3，v4，v5}，V={v2}，S点集扩充，v2为下一个最短路径顶点，路径长为41，D[]={0，41，10，21，16}；
Step5 S={v1，v2，v3，v4，v5}，V={}，V点集为空，结束算法。至此，得到从源点到其他各个结点的最短路径。
3 Dijkstra算法优化策略分析
Dijkstra算法是计算最短路径的经典算法,但在实际使用过程中，该算法耗费大量的计算时间和存储空间，在某些实际应用中产生冗余。所以需要进行优化。在评判一个算法优劣时，通常研究该算法的时间复杂度和空间复杂度。可见，可以从影响Dijkstra算法效率的关键“存储空间和时间效率”进行优化。
3.1 权值排序优化策略
问题：S集合中未确定最短路径的顶点无序存放在数组中，每一次选择权值最小的弧段必须将所有未选择顶点对应的数组元素完全扫描才能找到，在数据量较大的情况下，计算速度受到严重制约。
优化策略：将要扫描的结点按其对应弧的权值进行顺序排列，每循环一次即可得到符合条件的结点，大大提高了算法的执行效率[5]。
3.2 A*算法优化策略
问题：Dijkstra算法基于广度优先搜索策略，即从源点出发，通过权值迭代遍历所有其他结点后，最后得到从源点到其他各结点的最短路径。整个搜索好似一个圆形向外展开，直到到达目的地，这样的搜索方式是盲目的。很明显这样求解一定能找到最优解，但节点展开的数量和距离成级数增加，会导致大量无效点的搜索，大大的降低搜索的效率。
优化策略：采用改进的Dijkstra算法——A*算法。A*算法是人工智能运用在游戏中的一个重要实践,它主要是解决路径搜索问题。A*算法实际是一种启发式搜索。发表论文。所谓启发式搜索，就是利用一个估价函数judge（）评估每次决策的价值，决定先尝试哪一种方案。这样可以极大地优化普通的广度优先搜索。从Dijkstra算法到A*算法是判断准则的引入，如果这个判断条件不成立，同样地，只能采用Dijkstra算法。所以A*算法中的估价函数是至关重要[3]。
3.3 扇形优化策略
问题：Dijkstra算法的搜索过程好似以源点为圆心的一系列同心圆向外展开，搜索过程中没有考虑到终点所在方向或位置，搜索是盲目的。这样导致大量的无用临时结点被反复搜索，成为实际应用中的瓶颈。
优化策略：从尽量减少最短路径分析过程中搜索的临时结点数量，限制范围搜索和限定方向搜索考虑进行优化。那么这种有损算法是否可行呢？我们知道，现实生活中行进，不会向着目的地的相反方向行进，否则就是南辕北辙。所以，当所研究的网络可以抽象化为平面网络的条件下，也不必搜索全部结点，可以在以源点到终点所在直线为轴线的扇形区域内搜索最短路径。这样，搜索方向明显地趋向终点，提高了搜索速度，虽然抛弃了部分结点，但基本上不影响搜索的成功率[5]。
3.4 邻接点优化策略
问题：Dijkstra算法在提取最短路径结点时需要访问所有的未确定最短路径的结点，算法的时间复杂度为O（n2），如果只希望找到从源点到某一特定的终点的最短路径也不例外。结点数n越大，算法的计算效率和存储效率越低。
优化策略：只对最短路径上结点的邻接点作处理，不涉及其他结点。即（1）只从源点的邻接点集合中选择权值最小的结点作为转接点，将此转接点加入已确定最短路径的结点集合S中；（2）对此转接点的邻接点集合与S的差集中的结点的权值进行更新；（3）从S中所有结点的邻接点集合的并集与S的差集中选择权值最小的结点作为下一个转接点，并将此转接点加入S中。重复（2），（3）操作，直至所有的结点确定最短路径。优化算法在更新最短路径值与选择最短路径值最小的结点时，仅仅涉及相关结点的邻接点集合及S集合中所有结点的邻接点集合与S集合的差集，时间复杂度取决于转接点的邻接点的数量多少，减少了计算次数与比较次数[4]。
4 总结
在详细分析求解最短路径问题的经典算法Dijkstra算法的基础上，针对Dijkstra算法存在的问题介绍了几种优化策略。Dijkstra算法在不同的现实应用中，可以具体情况具体分析，从而得到算法的高效率实现。
参考文献：
[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，1997，186～190.
[2] 谢柏青，佘晓歌. 算法与数据结构[M]. 北京：高等教育出版社，2001，230～232.
[3] 陈益富，卢 潇，丁豪杰. 对Dijkstra算法的优化策略研究[J]. 计算机技术与发展，2006，16（9）：73～75.
[4] 章永龙. Dijkstra最短路径算法优化[J]. 南昌工程学院学报，2006，25（3）：30～33.
[5] 胡树玮，张修如，赵 洋.扇形优化Dijkstra算法[J]. 计算机技术与发展，2006，16（12）：49～51.
|
