一种基于STL的高效最短路径算法

李宽荣　陆通　高勇

摘 要：最短路径分析是网络拓扑中的一个重要的应用，它在地理信息系统、计算机网络路由等方面发挥着至关重要的作用。解决最短路径问题的经典方法是Dijkstra算法，时间复杂度为O（n2），在大数据量下效率低下而且使用邻接矩阵存储图形数据在一定程度上造成了空间浪费。该文在分析了Dijkstra算法的基础上提出来一种改进方法，该法使用STL容器来代替邻接矩阵来存储图形数据提高了查询效率，并且利用双队列来存储节点降低了内循环次数，减少了很多不必要的计算，从而降低了算法时间复杂度。STL容器的应用使得最短路径算法得到了扩展，在求解最短路径的同时还支持添加障碍点，增加开关节点等应用。

关键词：最短路径分析 Dijkstra STL

中图分类号：TP301.6 文献标识码：A 文章编号：1674-098X（2014）04（c）-0037-02

Dijkstra算法的最大不足之处是在于求解的是一点到网络中所有点的最短距离，而实际应用中更多的是求解指定两点之间的最短距离。求解到所有点的距离完全没有必要，从计算代价来讲也是一种极大的浪费。Dijkstra 算法中使用矩阵来存储图像数据，对于有N个节点的图形，需要存储N*N个数据，虽然可以使用对称性来减少数量，但在大数据量下仍不能很好解决问题。目前，很多基于Dijstra的算法都是在数据结构和分析效率两个方面来优化。

该文在分析了Dijkstra算法的基础上，利用STL的map和multimap容器来存储图形数据，方便了数据的存取，也节省了内存占用。在求解的过程中使用两个优先级队列来存储待处理的节点，减少了内循环次数，降低了算法的时间复杂度。同时，引入STL map作状态容器，使其支持对障碍点的分析。而STL multimap的引入又可以使原有的节点增加开关属性，从而支持对电力拓扑网络的分析。

1 Dijkstra算法优化

1.1 存储图形数据

由于网络中的节点之间的关系是多对多的关系，每一个节点可能关联多个节点，所以使用STL multimap来存储节点之间的关联关系。同时，为每一个节点建立一个状态标志，使用STL map来存储。Multimap和map使用的是红黑树结构来存储节点，所以具有较高的查询效率，而且内存空间是动态扩展的不需要事先计算需要的内存空间，能很好的解决从数据库中读取未知数量的数据的情况。

另外，multimap支持结构体来作键值，所以可以存储更多信息。比如，考虑到电力网络的节点，可以存储开关节点的状态信息。Dijkstra算法只是求解最短路径长度，但并不能得到具体的路径。而使用map来存储节点的状态信息StateInfo，可以用一个标识来记录最短路径上每个节点的前一节点。这样通过从目的点开始依次查询其前一节点直到起始点就能获取最短路径。StateInfo的引用使得求解最短距离算法得到进一步的扩展，比如，可以设置障碍点，所求的最短距离必须绕过障碍点。只需要设置给障碍点设置一个新的状态，就可以实现。

1.2 双队列的应用

另外一种数据结构是队列，用来存储即将进行探测的节点。本文中用了两个队列，并以优先级的高低区分。高优先级队列存放已经探测过但是最短路径需要更新的节点，低优先级队列存放第一次探测到的节点。高优先级的队列中的节点会被优先取出进行探测，因为高优先级节点有更高的概率到达目标节点。

1.3 高效算法的提出

为了进一步的提高计算速度，采用双队列来存储当前计算的节点信息，一个是高优先级对列HighQueue，一个是低优先级队列LowQueue。基本步骤如下：

（1）首先，利用STL multimap和map定义数据结构JointRealtionInfo，StateInfo来存储节点之间的关联关系和状态信息。然后，读取数据库信息到数据结构中，设定每个节点的状态信息初始值为Unchecked。

（2）定义两个队列：HighQueue、LowQueue，并将起始节点srcJointID加入LowQueue中，同时修改StateInfo中起点的状态StateInfo[srcJointID].state =checking，修改长度标签为0，表示当前节点距离起始节点的距离为0。

（3）判断HighQueue或LowQueue是否为空，若都为空，则直接返回终点节点DesJoint的长度标签值。若有一个不为空，则继续执行下一步。

（4）优先判断HighQueue是否为空，在为空的前提下再判断LowQueue。无论如何取不为空的队列的第一个元素值，赋值给临时变量TempJoint。

（5）统计JointRelationInfo中以TempJoint为键的个数amount（这里使用multimap：：count（）来统计）。使用multimap：：find（）来返回一个迭代器Iter指向第一个以TempJoint为键的键值对，通过Iter可以找到对应的值，即与TempJoint相邻的下一个节点的ID，以及TempJoint本身的长度和开关状态，若存在另外一个相邻节点，则使Iter++即能找到，这就是multimap的便利之处。

（6）判断如果amout>0，首先通过Iter找出第一个相邻的节点AbutJoint，并获取其自身的长度abutLen，将其与TempJointD的距离标签值相加得到NewMarkLen。并与AbutJoint的距离标签值abutMarkLen作比较。若大于，说明经过TempJoint到达AbutJoint的路径并不比当前AbutJoint的路径短，此时执行步骤（7）。若小于，说明经过TempJoint到达AbutJoint的路径要比AbutJoint原本的路径更短。此时执行步骤（8）。如果amount=0，说明TempJoint的相邻节点都已经遍历完，接下来执行步骤（11）。endprint

（7）使amount--，Iter++，并继续执行（6）。

（8）首先要判断TempJoint开关状态，若是打开，则说明此路不通。若是闭合则继续。修改AbutJoint的距离标签值为NewMarkLen，同时将AbutJoint的当前路径上的前一个节点priorJoint设为TempJoint。判断AbutJoint当前状态AbutState，若AbutState=CHECKED，则执行步骤（9）。若AbutState=UNCHECKED，则执行步骤（10）。

（9）AbutJoint状态为CHECKED说明已经存在从SrcJoint到AbutJoint的路径，但是经过TempJoint的路径要比之前的路径更短，所以需要更新原有的路径。判断当前的AbutJoint是否是目标节点DesJoint，若不是，则将AbutJoint加入到HighQueue中等待进一步的处理。然后，更新AbutJoint的状态为CHECKEING。执行步骤（7）。

（10）AbutJointz状态为UNCHE CKED，说明从原点SrcJoint开始探测的路径尚未有经过AbutJoint。此时判断AbutJoint是否是目标节点DesJoint，若不是将其加入到LowQueue中，并修改AbutJoint的状态为CHECKING。执行步骤（7）。

（11）设置TempJoint的状态为CHECKED，检测DesJoint的状态，判断目标点DesJoint是否已经被探测到，也就是说已经存在一条从原点SrcJoint到目标点DesJoint的路径。若DesJoint的状态为CHECKING，获取DesJoint的距离标签DesMarkLen，即SrcJoint到DesJoint的距离，执行步骤（12）。若为CHECKED或UNCHECKED，执行步骤（3）。

（12）经过上述11个步骤就可以完成从原点到目标点的最短路径搜索，为了进一步的优化，当目标点已经找到以后，将其距离标签DesMarkLen与当前HighQueue、LowQueue内节点的距离标签进行逐一比较，若队列中的节点的距离标签都要比DesMarkLen大，说明当前找到的起始点到目标点的最短路径即为最短的路径，不肯能再存在更短的路径。若队列中存在距离标签小于DesMarkLen的节点，则说明有可能存在到达目标节点更短的路径，不作任何处理继续。

2 结语

该文通过使用STL容器来存储图形中节点之间的关系，在降低内存占用的同时也加快了查询的速度，而且使原有的算法不再是单纯的求解两点之间的最短路径，还可以增加开关节点以及对障碍点的分析。采用高低优先级双队列，分解了算法的规模，降低了时间复杂度，进一步提高了求解最短距离的效率。

参考文献

[1] Stefano. Pallottino. Shortest-path methods： Complexity， interrelations and new propositions[J].Networks，1984（14）.

[2] 侯捷.STL源码剖析[M].华中科技大学出版社，2002.

[3] 王志和，凌云.Dijkstra最短路径算法的优化及其实现[J].微计算机信息， 2007，11（3）：275-278.

[4] 宁建红.最短路径算法效率研究[J].上海电机学院学报，2006（3）：38-41.

[5] 张红科.基于链表的Dijkstra算法优化研究[J].电脑知识与技术，2008（26）.endprint