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

一种基于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为