有向非负权图中经过必经节点集最短路径算法

杨志勇 ，叶冯彬 ，冯艳辉 ，刘秀秀 ，朱 岩

（1.中国科学院大学 北京 100049；2.中国科学院国家空间科学中心 北京 100190；3.成都理工大学 成都610059）

有向非负权图中经过必经节点集最短路径算法

杨志勇1，2，叶冯彬3，冯艳辉1，2，刘秀秀1，2，朱 岩2

（1.中国科学院大学 北京 100049；2.中国科学院国家空间科学中心 北京 100190；3.成都理工大学 成都610059）

传统的Dijkstra算法只是针对起点和终点求解最短路径，而不能解决从起点出发，经过必经节点集，到达终点的无重复节点且无回路的最短路径问题。为此，在有向非负权图中，提出了Dijkstra算法和回溯法相结合的方法。对Dijkstra算法改进，并求解关键节点（起点，终点和必经节点）间的最短路径，进而从关键节点所构成的矩阵中采用回溯法得到目标路径。通过实际的算法实现，测试大量的有向非负权图数据，证实了算法的有效性和正确性。

Dijkstra算法；回溯法；深度优先搜索；最短路径；必经节点集；有向非负权图

最短路径（SP）算法，可以用来解决道路设计和网络路由等诸多动态规划和优化的问题。EW.A Dijkstra于1959年提出著名的Dijkstra算法[1]，用于计算一个节点到其他所有节点的最短路径，其主要思想是以起点为中心向外一层一层辐射迭代，直到辐射到终点为止。

以Dijkstra为原型，研究人员提出了对最短路径问题[2-4]的诸多优化方案。针对Dijkstra算法的复杂性，提出一种新的时空复杂度更低的改进算法[5-7]；采用配对堆结构实现路径计算过程中的优先级队列的一系列操作，提高算法的效率和性能[8]；对Dijkstra标号法改进，实现起点和终点之间的最短路径[9]；通过对每个顶点增加前置邻结点属性，并实时记录和更新，求解多条路径问题[10]。

以上算法是针对只有起点和终点的研究，而生活中还存在一类有待研究又有着重要意义的问题：1）网络路由经过必经路由节点问题。网络数据包发出后，必须经过几个关键路由节点，这些关键路由节点需要对网路数据包进行审查。2）公交线路设计问题。设计一条公交线路，使得公交车从始站出发，经过重要的站点到达终点站的行驶路径最短[11]。如，逐渐扩大占地面积的校园中，教学楼、学生宿舍、餐厅、体育场更加分散。因此，需要设计一条便捷的交通线，以节省校园师生路途时间[12]。3）军事运输路径寻优问题。设计一条军事人员及物质运输线路，该线路必须通过一些重要的城市、桥梁、加油站、弹药库等地点，以满足作战需求[13]。

1 问题描述

如图1所示，求解以0为起点，经过必经节点2、3节点，到达终点1的最短无重复节点的路径。

图1 4个节点有向带权拓扑图

以0为起点，经过2、3节点到达终点1的路径有：0-＞2-＞3-＞1，权值为4；0-＞3-＞2-＞1，权值为5。因此，最短路径为0-＞2-＞3-＞1。

1.1 概念定义

必经节点：最短路径中必须包含的节点。

关键节点：起点、终点和必经节点统称关键节点。

自由节点[14]：除关键节点以外的其他节点。

弧头节点：指的是有向边的目标节点。

弧尾节点：指的是有向边的源节点。

1.2 问题定义

在一个有向非负权稀疏图中，给定任意的起点，必经节点和任意终点。要求寻找一条从起点出发，经过所有必经节点，到达终点的无重复节点无回路的最短路径。在这条最短路径中，可能会经过网络中除起点、终点和必经节点以外的自由节点。

2 必经节点最短路径问题算法分析

文中将庞大的稀疏图，分解成几个易于求解的子问题，然后再全局求解最短路径。因此，对求解稀疏图必经节点的最短路径问题，可以分解为两个过程：1）求解关键节点间的最短路径，将庞大的有向非负权稀疏图简化为关键节点间的稠密图（关键节点到关键节点的路径上的自由节点隐藏）；2）在关键节点间的稠密图中，寻找一条从起点出发经过所有必经节点到达终点，且无重复节点无回路的最短路径。

3 关键节点间最短路径

所谓关键节点间的最短路径，就是求解所有关键节点到其他关键节点的最短路径，某一个关键节点到其他某一个关键节点的最短路径中无其他关键节点。例如，设关键节点A、B、C、D，则A到B的路径中，不包含其他的关键节点C和D，且该条路径中无重复的自由节点。

文中采用了邻接链表的存储方式，并在求解关键节点间的最短路径时，阻止遇到的关键节点向外辐射的方式对Dijkstra算法改进，实现将所有稀疏网络图中的节点简化成所有关键节点间的最短路径稠密图。

3.1 数据结构设计

1）存储网络图的邻接链表数据结构

2）dijkstra算法计算时的辅助结构

3）存储关键节点间最短路径的数据结构

3.2 关键节点间最短路径算法实现步骤

1）将节点的信息读取到图数据结构体中；为所有辅助节点结构分配内存空间。

2）将每个单点辅助结构进行初始化：a）currentID设置为该单点的序号；b）passed设置为false（表示未经过）；c）weight设置为无穷大（表示不可达）；d）parent设置为-1（表示为没有父节点）。

3）选定一个没有计算过且非终点的关键节点作为改进版的 Dijkstra运算的源节点SourceKeyVertex，作为Dijkstra计算的扩展节点，并将与关键节点ID一致的单点辅助结构初始化：a）passed设置为true（表示经过）；b）weight设置为0（表示起点）；c）parent设置为-1（表示为没有父节点）。

4）更新与当前扩展节点相连的所有弧头节点在辅助结构中的信息，满足以下条件的节点更新：a）该弧头节点未经过；b）源关键节点到扩展节点的权值与当前扩展节点到弧头节点的权值之和newWeight小于之前对该弧头节点更新的权值oldWeight；c）该弧头节点不是起点。

更新内容包括：a）弧头节点的权值更新为newWeight值；b）弧头节点的父节点更新为当前扩展节点。

5）在辅助结构中寻找新的扩展节点，步骤如下：a）从辅助结构中找到未经过的、有后继节点且权值最小的节点expandVertexTmp。若expandVertexTmp为关键节点，那么设置expandVertexTmp为经过，即设置passed为true，重复当前步骤；若expandVertexTmp为自由节点，则将expand-VertexTmp作为新的扩展节点，并将passed设置为true，重复第4步骤。b）若未找到符合要求的最小权值的节点，那么本轮以关键节点SourceKeyVertex作为源节点的Dijkstra的运算结束，转到第6步骤。

6）在所有关键节点到关键节点信息的数据结构KeyVertexInfo中，找到与SourceKeyVertex的ID相同的位置，存储SourceKeyVertex到其他关键节点的路径信息。重复步骤2，继续选定一个未计算过且非终点的关键节点，计算到其他关键节点的路径，直到所有的关键节点都计算了到其他关键节点的路径为止。

4 经过所有关键节点的最短路径

稀疏图转换为关键节点间的链接稠密图后，这就转换为查找一条从起点出发，经过所有的必经节点，到达终点的最小权值路径问题。

4.1 数据结构设计

1）采用计算关键节点间最短路径的数据结构。

2）深度优先搜索时不作为扩展节点的关键节点信息存储栈。

std::stack＜Assist＞ onePointAssistStack；

3）深度优先搜索时所找到的一条最短路径的存储结构。

std::stack＜unsigned int＞ minWeightPath；

4.2 经过所有关键节点的算法实现步骤

1）初始化每个单点辅助结构，将起点作为扩展节点，并设置起点的相应信息，与改进Dijkstra运算中的步骤2、步骤3相同。

2）判定是否经过了所有的关键节点，新的扩展节点为终点，并且到达终点的权值比之前到达的权值小。a）若满足要求，则清空minWeightPath存储结构中的路径信息，并存储该条路径中的所有节点（关键节点和自由节点）编号。转到第4步骤。b）若不满足要求，转到第3步骤。

3）查找一个新的扩展节点（关键节点）。判定当前扩展节点到其他关键节点路径的有效性，即到其他关键节点的路径上的自由节点不在起点到达当前扩展节点路径中；所判定的关键节点未经过；未提前到达终点；到所判定的关键节点的权值未超过已有路径的最小权值：a）若扩展节点到其他的关键节点有效，将当前扩展节点到新的扩展节点路径中的自由节点更新为经过，以及更新相应的父节点值。并将第一个有效的关键节点作为新的扩展节点，其他有效的关键节点压入关键信息存储栈中，重复第3步骤。b）若扩展节点到其他的关键节都无效，转到第4步骤。

4）判定关键信息存储栈是否为空。a）若栈为空，结束回溯深度优先搜索算法；b）若栈不为空，从关键信息存储栈中弹出一个关键节点，并将该关键节点作为新的扩展节点。将原扩展节点（关键节点）到新扩展节点的父节点所在路径上的节点的信息设置为未经过；更新新扩展节点在辅助结构中的状态；更新新扩展节点到其父节点（关键节点）路径上的自由节点的状态。重复第2步骤。

回溯深度优先搜索过程，步骤3判定节点的有效性保证了所求得的路径中无重复节点无回路。回溯深度优先搜索的方式保证了搜索出来的结果肯定是满足条件且全局最优的结果，即该条路径是从起点出发，经过所有的必经节点，到达终点无重复节点无回路的最短路径。

5 算法实例测试

算法运行环境为Ubuntu14.04.132bits系统，2.2GHz T6670CPU，3GB内存，编程语言C++，编译器为GCC4.8.2（编译时采用O2优化）。算法测试用例均来自2016华为软件精英挑战赛初赛[15]试题提供的数据。

挑战赛的题目：给定一个带权重的有向图G=（V，E），V 为顶点集（顶点不超过 600 个，每个顶点的出度不超过8），E为有向边集，每一条有向边均有一个权重。对于给定的顶点s、t，以及V的子集V'（元素个数不超过50），寻找s到t的不成环有向路径P，使得P经过V'中所有的顶点[14]。

5.1 程序运行中间结果

本实验从文献[15]所提供的数据中，选取测试用例观察程序运行的中间结果。为了降低检验中间结果的复杂性，该测试实例选用在20个节点中，起点为2，终点为19，必经节点为3、5、7、11、13、17，找出一条经过必经节点的最短路径，网路节点数据所形成的网络拓扑结构如图2所示。

图2 20个节点的有向带权拓扑图

通过Dijkstra运算后，关键节点间的路径如表2所示。关键节点间的权重值的稠密矩阵关系如表3所示。其中，关键节点间的简化链接，可能是经过自由节点才能到达的。

表1 关键节点间的路径

以表1的第一行为例，表示的关键点2到关键点3的最短路径权值为18，其中需要经过自由节点15和18。Path中没有自由节点，表示的是源关键节点直达目标关键节点。

表2 关键节点间的权值稠密矩阵

以表2的第二行为例，表示的是关键节点3到达其他关键节点的情况。其中，能够到 5、11、13、17和19共5个关键节点；不可达的关键节点为2和7。

转换成稠密矩阵之后，采用回溯深度优先搜索的方式进行搜索，最短路径（权值71）如下：

2-＞15-＞18-＞3-＞11-＞7-＞13-＞4-＞5-＞6-＞17-＞19

中间结果的总体观察结果，表明该算法能够准确的找出满足条件的最短路径，且无重复节点。

5.2 测试在不同节点下运行的时间效率

在计算关键节点间的最短路径和计算得到最终结果处设置计时器，记录计算节点间最短路径的平均花费时间和找到最短路径时总的平均花费时间。由于文献[15]所提供的数据的最大节点个数为600个节点。因此，设定测试节点总数分别为180个，300个和600个，并且设置必经节点数目为10个、15个和20个。多组数据测试平均结果如表3～5所示。

表3 180个节点数运行时间

表4 300个节点数运行时间

表5 600个节点数运行时间

从测试结果可以看出，对于庞大的网络图中，必经节点数目较少时，程序运行的时间非常的可观，比文献[14]中的运行时间缩短了几十倍。

6 算法复杂度分析

在计算关键节点间的最短路径时，采用的是传统的实现方式。理论上该算法的时间复杂度为。但在计算关键节点间的最短路径时采用遇到关键节点直接终止关键节点向外辐射的方式[16]，大大减少扩展节点向外辐射的链接数，使算法更加快速的收敛，降低算法运算的复杂度。测试结果表明，在计算关键节点间的最短路径所需要花费的时间对总节点数和中间节点数都不敏感。只是在回溯深度优先搜索查找经过所有关键节点的最短路径时，对必经节点个数非常敏感。必经节点数增加，将按照阶乘的方式增加，运算量很大。因此，在关键节点数不超过回溯深度优先搜索接受范围内，也能快速的对整个稠密图的最短路径查找。该算法只能针对较少关键节点数的问题，在以后的研究中可以重点研究关键节点间查找最短路径问题。

7 结束语

对于网络路由经过必经路由节点问题和公交线路设计问题，都可以采用将庞大的有向稀疏图简化成关键节点的稠密图，并搜索得到满足条件的最短路径的方法进行求解。总的来说，该算法面对大规模的有向稀疏网络图，提出了新的求解最短路径问题的算法思想。但还需要进一步的研究和改进该算法，以解决海量的网络节点数和大量的必经节点数情况下的最短路径问题。

[1]Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959（1）:269-271.

[2]李娟，张婷，李元香.基于改进演化算法的最短路径问题研究[J].计算机应用与软件，2015，32（9）:244-245，273.

[3]刘荷花，翟超，陈晶.一种改进的遗传算法求解旅行商问题[J].北京理工大学学报，2013（12）:139-142.

[4]牟衔臣，谢东来，闫威，等.基于遗传算法航路规划TSP问题的研究[J].系统仿真学报，2013:190-196.

[5]张锦明，洪刚，文锐，等.Dijkstra最短路径算法优化策略[J].测绘科学，2009，34（5）:105-106，99.

[6]Orlin JB，Madduri K，Subramani K，et al.A faster algorithm forthe single source shortestpath problem withfew distinct positivelengths[J].Journal of Discrete Algorithms，2010，8（2）:189-198.

[7]王智广，王兴会，李妍.一种基于Dijkstra最短路径算法的改进算法[J].内蒙古师范大学学报，2012，41（2）:195-200.

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

[9]王树西，吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学，2012，39（5）:223-228.

[10]金婷，方欢，方贤文.改进型Dijkstra算法的最短路径求解[J].软件导刊，2016，15（2）:129-131.

[11]姚广铮，孙壮志，孙福亮，等.北京奥运公交专线规划及评价方法[J].城市交通，2008，6（3）:29-34.

[12]薛瑞，张永显.校车最优路径规划算法研究[J].重庆科技学院学报：自然科学报，2015，17（5）:68-71.

[13]徐庆征，柯熙政.必经点最短路径问题模型及相应遗传算法研究[J].系统工程与电子技术，2009，31（2）:459-462.

[14]黄书力，胡大裟，蒋玉明.经过指定的中间节点集的最短路径算法[J].计算机工程与应用，2015，51（11）:41-46.

[15]2016华为精英挑战赛初赛试题[EB/OL].（2016-03-04）[2016-04-27].http://codecraft.huawei.com/home/detail.

[16]熊扬宇，宋鹏，王建余，等.紫外光通信网节点设计与性能分析[J].西安工程大学学报，2016，30（6）：797-801.

Algorithm for finding shortest path which contains a necessary set of nodes in directed and non-negative weighted graph

YANG Zhi-yong1，2，YE Feng-bin3，FENG Yan-hui1，2，LIU Xiu-xiu1，2，ZHU Yan2
（1.University of Chinese Academy of Sciences，Beijing 100049，China；2.National Space Science Center of Chinese Academy of Sciences，Beijing 100190，China；3.Chengdu University of Technology，Chengdu 610059，China）

Traditional Dijkstra algorithm can get the shortest path with start and end，but it can not gain the shortest path which starts from start，goes through the necessary set of nodes and arrivals the end without duplication and loop.Therefore，put forward the idea to combine Dijkstra algorithm and backtracking algorithm in directed and non-negative weighted graph.Using the improved Dijkstra algorithm solved the shortest path between the key nodes（including start，end and the necessary set of nodes）.And then，backtracking algorithm with depth-first search methodobtained the target path from the matrix composed of key nodes.The result confirms the validity and correctness by testing a large of directed and non-negative weighted graph data with code of the algorithm.

Dijkstra algorithm；backtracking algorithm；depth-first search method； shortest path； a necessary set of nodes；directed and non-negative weighted graph

TP393

A

1674－6236（2017）16-0032-05

2016-06-29稿件编号：201606224

杨志勇（1990—），男，四川仁寿人，硕士研究生。研究方向：信息获取与处理、计算机网络路由。