基于Dijkstra算法的优化策略研究
2019-05-08冷思佳
冷思佳
摘 要：Dijkstra算法不断改进，通过探索最短路径来处理现实生活中的问题，为生产、生活提供便利。本文简要介绍Dijkstra算法原理，在此基础上，重点探究Dijkstra算法优化策略，尽可能发挥这一算法实践指导作用，希望这一论题能为研究人员提供参考。
关键词：Dijkstra算法;优化;策略分析
中图分类号：TP301.6 文献标识码：A 文章编号：1671-2064（2019）06-0034-02
0 前言
近年来，智慧交通由于其低成本高效率高可靠性，在封闭园区、港口等场景下得到了越来越多的应用，已经成为一种新的趋势，得到了我国学者的高度关注。要实现交通的智慧化，只有在道路数字化与车辆联网化的基础上，再引入车路协同的控制机制，由统一的调度算法来对车辆的行驶进行控制，这就离不开Dijkstra算法的研究和优化。
1 Dijkstra算法含义
Dijkstra算法，即迪杰斯特拉算法，运用该算法能够计算出以中心节点为基础到达其他所有节点的最短路径。Dijkstra算法是计算最短路径算法的主要代表，许多学科中均涉及对它的介绍，例如，图论、运筹等。Dijkstra算法表现形式分为“永久和临时标号”以及“OPEN，CLOSE”两种。
2 Dijkstra算法原理
Dijkstra算法是在最短路径算法的基础上发展而来，以无向网络为视角，随着网络范围的不断变化，最短路径中的部分节点固定不变，对此，应优化算性能，这为Dijkstra算法提供了广阔空间。Dijkstra算法运行的过程中，以降低复杂度、缩小节点范围为目的，同时，大大提高运行效率，运用新型算法处理节点问题[1]。
Dijkstra算法为追求最短路径，利用标记法实现这一目标，基于源点寻找短节点，并以新节点为起点，通过迭代方式寻找段路径。具体过程：网络中设置集合M和集合N，其中，前者在计算的基础上融入最短路径节点，后者处于最短路径节点边缘处。如果单一节点yj的对参数为（Cj.Sj），C是从源节点y到节点yj的最短路径，Sj表示节点yj在最短路径的父亲节点。
首先，初始化操作。M=Ф，N包含全部节点，设置节点Cj=∞，Sj=[.]。其次，yj加入集合M，并从N中删除，设置Cs=0，Ss∈Ф。然后，检验M中节点yi到N中节点yj的距离Lij，需要注意的是，yi与yj应保持连接状态，设置Cj=min[Cj，Ci+Lij]。接下来选取Cj最小节点yj，并从N集合中删除，将其融入集合M，此时形成的节点即最短路径新节点（x）。最后寻找x的父亲节点Sj，具体记录节点参数（Cj.Sj）。待网络节点加入到M集合后，这时N=Ф，Dijkstra算法原理整个过程顺利完成[2]。
3 Dijkstra算法优化策略
3.1 优化思想
Dijkstra算法要满足智慧交通多车辆并发的要求，就需要考虑对算法进行优化，通过渗透优先队列改进算法确定优先级，因此，能够自行设置起点，合理调整顶点优先级。据调查可知，优先队列有效运用，能够在一定程度上降低算法复杂度，大大提高算法效率。为简化起见，本文仅讨论针对单一车辆终端的调度算法优化，多车辆并发所涉及到的多线程调度等不再本文讨论范围内。
3.2 优化设计
3.2.1 设置参数
在加权无向网络中，的V和E分别表示节点集合和边集合，节点用n表示，边用m表示。G中节点用u表示，节点间的边用e表示，权值用表示。最短路径数用表示，其中，、、分别表示根节点到节点最短路径距离、父亲节点、根节点最短路径节点集合。针对加权无向网络内部节点设置状态参量，状态参量表示为，该向量值为1时，意味着节点数值保持不变，无需处理。当该向量值为0时，意味着节点应不断更新。
3.2.2 算法描述
网络G中，根节点成功构造，如果其中某边的权值动态变化，那么应确定受影响的范围。针对算法描述时，应细分两种情况，第一种情况即权值增大，第二种情况即权值减小。当权值增大时：如果SPT的边权值并未增大，那么各节点最短路径的长度已经达到最小，所以对于SPT的结构没有影响;如果SPT的边权值增大，那么网络中的位置就可能不是路径最短的位置，所以需要及时调整节点的位置。当权值减小时：如果SPT的边权值并未减小，需要比较发生变化的边对应节点的最短路径，必要时可以修改其中一个节点的父亲节点;如果SPT的边权值减小，则需要找到子节点，在其他节点的最短路径发生“聚集”时，确定权值变更的影响范围。这里需要注意的是，如果更新节点最短路径的值变小，那么就会影响与之相连的节点，所以需要考虑各个节点对应的项，一般都将这些项归入一个集合中。
3.3 实例分析
3.3.1 封闭园区
Dijkstra算法应用于封闭园区（例如港口）的调度规划，以往港口场地选址方法主要为经验数据法，这种方法實际应用时，方法的时效性较低，且易与经验数据直线距离存在偏差。同时，多台车辆并发处理不同任务安排时，通行规划会产生相互之间的影响，这些因素导致调度准确性大大降低，这与车辆沿港内道路行驶的实际需求存在偏差。应用Dijkstra算法完成集卡调度场选址任务，在这一过程中，合理确定起点和终点，同时，确定路径算法节点，求得最短路径算法，大大提高调度场选址准确性。
Dijkstra算法应用分析：设置权有相图M=（），在其中包括道路节点数量以及距离，针对顶点集合以及节点路径具体分析。首先，集合M仅包括源点，即M=源点，节点间距离为0。集合P包括除源点外所有顶点，以及节点距离。其次，从集合P中选择距离源点最小顶点集合融入到M中，并重复这样的操作，进而能够得出源点到不同节点的最短距离。然后，以目的点距离为出发点，针对源点和目的点的中间点全面记录，与此同时，适时调整集合P中顶点距离，如果源点与顶点间距离小于初始距离，那么将源点与顶点距离设置为最短距离。最后，重复上述操作，待所有顶点融入到集合M中。
3.3.2 机场滑行
Dijkstra算法应用于机场滑行（例如海口美兰国际机场），美兰机场是我国4E级国际机场，美兰机场单跑道长度是3600m，宽度是45m，真方位角是90与270度。飞机滑行网络包括机坪滑行道、主滑行道、快速脱离滑行道与停机坪滑行道。该机场由17个近停机位、16个远停机位共计33个停机位组成。美兰机场的飞机起降操作原则是中型机从R6口脱离跑道，大型机从R5口脱离跑道。本案例选择2016年8月份某日07：50到13：30的航班时刻运用Dijkstra进行优化计算，探究Dijkstra在确定机场最短滑行路径方面的作用。
Dijkstra算法应用分析：设置G=
3.3.3 应急物流
Dijkstra算法也常常需要在应急物流路径规划中得到应用，需要将时间当成是路径规划的首要目标。不同于常规情况，应急物流不将路程当成是路径规划问题的权重，而是以时间为道路权重。在某地突发事件中，要求将应急物资从应急仓库v1运送到需求点v7，之间经过5个道路节点，即v2-v6，应急车辆可双向行驶，要求通过车辆路线规划在最短时间内完成物资运输。在遥感卫星支持下，道路一旦中断物流指挥控制中心可以进行路况把握，指挥车辆改变行驶道路。
在算法应用过程中，可以将路线规划问题描述为从仓库到物资运送需求点共包含7个阶段，构成了包含有限条道路的通道。在车辆通过各道路所需时间已知的情况下，对道路中断概率和概率密度分布进行考虑，搜索时间最短的路径。由于各道路中断时间概率密度函数服从均匀分布，同时道路中断点距离上一节点需要时间同样均匀分布，因此可以采用优化Dijkstra算法进行路径规划，先对起点v1到点vj权值和T1j进行初始化，然后对点到该点连通未计算的点的权值进行计算，从未计算点中进行T1j最小点的选取，直至完成所有节点计算可以实现最短时间的路径搜索。应用优化算法得到路径为1→3→6→7，需要9h时间达到需求点。相较于经典Dijkstra算法，能够缩短12.9%的时间。由此可见，在应急物流路径规划中应用Dijkstra算法，可以使运输时间得到有效缩短。
3.4 算法改进分析
3.4.1 算法应用问题
从算法应用情况来看，在网络节点较少的情况下，采用Dijkstra算法核心步骤就是从未选定为最短距离的网络节点中进行当前集合中权值最小的点的选择，需要实现步骤的循环操作。在网络节点较多的情况下，不采用比较筛选策略需要对未标记的点进行循环比较，最终导致最优路径计算速率受到制约。受这一因素的影响，在网络节点数量较大时程序正确性难以得到有效把握，将导致节点操作性较差，不利于算法的应用。
3.4.2 算法改进建议
针对算法应用问题，需要采用添加网络节点标记flag的方式进行算法改进，使算法应用效果得到保证。具体来讲，就是利用布尔值类型数组flag实现算法节点标记。在网络节点被选定为最短距离的情况下，需要进行ture标记，否则进行flase标记。在初始化操作的过程中，需要将所有节点标记为flase。随着算法的进行，逐步完成选定节点的修改，能够在循环操作完成后实现所有节点标记，得到节点对应flag标记值。针对未选定节点进行最小权值的筛选，由于选定节点均标记为ture，因此只要进行false值节点选择就能迅速完成目标查找。除了对节点进行标记，针对为确定最短距离的网络节点，可以进行数值标记。在实际操作中，可以利用整型变量min进行标记，从而通过比较实现最小距离的筛选。在初始化操作中，可以将min定义成最大值。在数组遍历的过程中，min将不断减小。实际进行节点判别时，应当确保节点flag标记值为flase，同时还要确保min当前min要小，才能完成网络节点重新赋值，同时对当前节点标记号进行记录。如果不能同时满足这两个条件，可以直接跳过。采用该种方法，只需要一次循环就能在每次搜索中进行未标记网络节点最小权值的查找，因此能够使算法效率得到提高。采用改进后的算法进行路径规划可以发现，无论是在交通管理还是物流疏散等方面，算法都能得到快速执行。出现这种情况，与算法节点计算量的减少有关，因此采用优化算法能夠获得较好应用前景。
4 结语
综上所述，Dijkstra算法优化后，算法性能会大大提高，能够为节点变化情况作出详细解释，并在短时间内提供最优路径，同时，算法研究人员能够以此为借鉴，在理论补充的前提下，为实践活动提供理论指导。此外，Dijkstra算法应用前景会越来越广阔，能为生活中实际问题处理提供理论依据，因此，研究学者应深入探究，为Dijkstra算法改进提供思路和建议。
参考文献
[1] 房敏.浅谈Dijkstra算法的相关改进[J].计算机产品与流通，2017（10）：212.
[2] 卢飞.基于Dijkstra算法的集装箱港口集卡调度场规划研究[J].中国水运，2017（01）：48-49.
[3] 王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41（6）：217-224.
