基于Dijkstra算法的优化研究

易文静　田俊峰

摘要：最短路径算法的研究及其应用在各个领域都起着重要作用，例如交通领域的最优路线，军事领域的行军路线，网络通信领域的路由选择等。该文将对最短路径问题中最经典的Dijkstra（迪杰斯特拉）算法进行介绍和优化改进。笔者将这种优化改进后的算法称之为：DJ_ray算法，意思是对Dijkstra算法进行发散性思想优化。该文将会对传统的Dijkstra算法与优化后的DJ_ray算法，在思想、原理、实现方法、数据结构上进行说明比较，并从时间及其空间复杂度上进行分析对比。同时，为了更好地展示DJ_ray算法在实际应用中的优点，文本将以DJ_ray算法优化火车交通网络路线为案例来进行阐述。

关键词：最短路径；交通路线；Dijkstra算法；DJ_ray算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）23-0166-03

Abstract： Research and application of the shortest path algorithm plays an important role in every field， such as the optimal route in the field of transportation， travel route in the field of military， routing in the field of network communication， etc.As a result， the efficiency of the shortest path algorithm in practical application of product development still need to continuously improve.This article will be to the shortest path problem is one of the most classical Dijkstra （Dijkstra） algorithm is introduced and the optimization improvement.I will improve after this optimization algorithm called： DJ_ray algorithm ，meaning： the Dijkstra algorithm to optimize divergent thinking.This article will be to the traditional Dijkstra algorithm and the optimization of the improved DJ_ray algorithm， in the thought， principle， method， data structure are compared， and explain and analysis comparison from time and space complexity.At the same time， in order to better display DJ_ray algorithm advantages in practical application， the text will be DJ_ray algorithm in GIS， the train traffic network route as a case， through a combination of theory and practice for everyone.

Key words： shortest path； traffic routes； Dijkstra algorithm； DJ_ray algorithm

1 绪论

最短路径问题是图论中非常重要的最优化问题之一，也一直是计算机科学、交通工程学、地理信息系统（GIS）、运筹学等学科领域研究的热点。为了清晰的向大家展示其作用，以下我将通过火车最优路线选择的案例进行阐述Dijkstra算法。该算法是目前交通网络图在单源最短路径问题上运用最普遍、完善的算法之一，也是目前公认在非负权值，且所有的权大于等于零时，寻求最短路问题最好的算法，但是这样的方法依旧存在一些缺陷，如果不对这些缺陷进行完善改进而直接投入实际生产中，必将会造成不必要的损失。

本文将分为以下四个部分：第一部分概述Dijkstra算法在案例中实现的意义。第二部分介绍Dijkstra算法，并提出算法优化改进的方案—DJ_ray算法。第三部分描述DJ_ray算法的实现过程和复杂度分析。最后总结，指出文章的意义。

2 Dijkstra算法在案例中实现的意义

火车最优路线选择主要体现在以下三个方面：费用最少、里程最短、换乘次数最少。而这三个都可以通过Dijkstra算法计算得到，其中里程最短这个功能最为突出。Dijkstra算法实际上给出了寻求从一个给定点vi到任意一个点vs的最短路径。因此，先明确出发地与目的地两者之间火车能经过的所有地方，将它们看作是定点，其次知道火车所经过相邻两地方的里程，将里程看作是两点的权值，之后便可以用Dijkstra算法进行运算得出最短路径，即行程的最短路线。

3 介绍Dijkstra算法和提出算法优化改进方案

3.1 介绍Dijkstra算法

3.2 提出算法优化改进方案—DJ_ray算法

在上述的判断过程中，v4、v6和v10都当做过P标号，也对这些结点下所在的弧统统进行运算判断，可是在运算过程之前完整的查阅一遍整个网络图，就可以清楚地发现v4、v6和v10所在弧的轨迹明显偏离了正在求解的最短路径这条轨迹，但是出于这些点都是P标号点，用Dijkstra算法进行运算求解就必须对这些结点进行搜索判断，直到它们不符合运算要求了，才将它们筛除出列。由于传统的Dijkstra算法在每次判断最小权值的结点时，都需要对所有具有P标号点下的弧进行求解判断，而这些具有P标号的结点又是无序分布的，因此在判断过程中，会出现某些结点被多次判定的情况，甚至出现上述呈现的具有P标号的结点并不能到达最终结点的现象，对于以上种种情况要是在大的数据量下求解，必将会增加更大额外运算量，花费更多的排查时间，使该算法在解决实际问题中的效率大大减低。

为了使Dijkstra算法在实际运用过程效率更大化，对Dijkstra算法进行发散性思维的优化，并将优化后的算法命名为DJ_ray算法。以下是DJ_ray算法优化的两大方向：第一点，传统的Dijkstra算法是对图中所经过的每一个点都进行了判断，倘若在求解最短路径之前对所有的结点对象进行一个排序的预处理，使得每次求解最小权值时不需要对所有的P结点进行判定。而这种预处理方法可以运用数据结构中图的遍历中的深度优先搜索，从起点出发到终点结束，引出若干条连通的线段，将各线段上的结点作为最短路径问题求解所涉及的结点选出，之后对这些结点进行广度优先搜索，层次排序。 第二点，将上述所选择的这些结点作为数据结构中单链表的结点，然后先将各个结点进行面向对象的封装，之后通过map（key，object）方法将封装好的类的key键放入在单链表的指针域next中，将映射出来的object对象（即封装类数据）作为单链表结点中的数据域data值。这样就可以在搜索过程中，不必花费大量的时间和存储空间， 从而大大提高算法的效率。

4 DJ_ray算法的实现过程和复杂度分析

4.1 DJ_ray算法的实现过程

1）深度优先搜索

通过图2与图1进行比较可以看出结点v4、v6、v9和v10已经在深度优先搜索中直接筛除出列，事实上，从图1便可以很清楚地看见这四个结点所在的路线并不能抵达终点v8.所以，进行该优化步骤能避免传统的Dijkstra算法盲目取点搜索缺陷，不仅减少运算量、缩短时间，还减少存储空间资源。

2）广度优先搜索

然后对进行了深度优先搜索的起点vi到终点vs连通子图进行广度优先搜索，其搜索目的在于确定各结点在子图中的层次关系，需对各结点做合理的分层安排。DJ_ray算法对分层问题也进行了最优分层处理。所谓的最优分层是指，将子图中涉及求解的所有结点分布在离起点最近的一层。如图3列车单行线广度优先搜索子图。

广度优先搜索先用最优分层排序法，确定各结点所在的层次，再确定各层结点间是否存在联系，为后续结点对象存储在单链表提供方便。在使用Dijkstra算法求解最短路径时，是根据各结点间的权值来判定最终选哪个结点作为下一个P标号，DJ_ray算法也不例外，而将各结点放置在离起点最近的层次，这样该点若是在最终的最短路径线路上也可以最快地找到，比它权值大的结点均可直接筛除出列，这种方法即快捷又人性化。

3）面向对象封装

最后采用Java语言的面向对象的思想，配合单链表的存储结构，使案例中交通网络图在搜索过程即快捷又准确。根据对象具有封装性、继承性、多态性特征，有利于清晰地表达多个不同类型的数据域，创建一个空对象，把筛选好的其中一个结点位置、结点的相邻边、结点的相邻结点、起点到该结点的最短路径长度等多种信息，设置在这个空对象中进行封装。然后使用Java语言中的Map（key，value）方法，将value（即封装好的对象数据）通过key键映射出来。接着将key键指向单链表上结点的指针域，value值则映射在单链表中结点的数据域中。由于封装后的对象具有复用性，可以避免一个结点在多次判定是进行多次运算求解，这种方式既节省了许多存储空间，又大大缩短了运算的时间。

4.2 DJ_ray算法复杂度分析

5 结束语

通过火车最优路线选择案例，介绍了一种优化后的求解最短路径问题的算法——DJ_ray算法，该算法是通过对Dijkstra算法在物理结构、数据结构和存储结构上进行优化改进后创建的新算法。先通过两种优先搜索方式对网络图中的结点进行排余、排序处理，然后再用面向对象的特性对筛选后的结点进行封装管理，接着参照Dijkstra算法的基本思想通过键值对的方式，将键指向作为存储结构的单链表结点指针域上，而值则映射在单链表结点数据域中。DJ_ray算法不仅能缩短运算周期，还减少了存储空间，在实际运用中能高效的处理问题。本文只是对交通网络图的单行线路进行了Dijkstra算法的优化改进，至于双向线路网络图效果如何？或是使用何种算法更有效的处理双向线路图？如何对这种算法进行优化改进？而这些种种问题都需要我们去研究、去发现。

参考文献：

[1] 吴祈宗. 运筹学[M]. 3版.北京： 机械工业出版社， 2013.

[2] 耿国华. 数据结构（用C语言描述）[M]. 北京： 高等教育出版社， 2011.

[3] 龚枥. 图论与网络最优化算法[M]. 重庆： 重庆大学出版社， 2009.

[4] 贺景. 交通咨询系统的最短路径算法与实现[J]. 西安财经学院学报， 2015（5）.

[5] 古凌岚. GIS最短路径分析中Dijkstra算法的优化[J]. 广东： 计算机与数字工程， 2006，34（12）：53-55.

[6] Michael King.A mini max method for finding the best differentiated paths[J]. Geographical Analysis， 1997，29（4）：298-313.

[7] 程理民.运筹学模型与方法教程[M]. 北京： 清华大学出版社， 2002.

[8] 董俊， 黄传河. 改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J]. 武汉大学计算机学院学刊， 2012，39（10）：245-247.