节点约束型最短路径的分层Dijkstra算法

康文雄 许耀钊

(华南理工大学 自动化科学与工程学院, 广东 广州 510640)

节点约束型最短路径的分层Dijkstra算法

康文雄 许耀钊

(华南理工大学 自动化科学与工程学院, 广东 广州 510640)

针对节点约束型最短路径问题,提出了基于回溯法的分层Dijkstra算法,通过分层结构寻找局部最优解来求得全局最优解或次优解.该算法利用分层结构可保存搜索进度的优势,使其在寻找过必经点最短路径时可以实现对搜索进度的保存与回溯等操作.实验结果表明:分层Dijkstra算法虽然增加了一定的空间复杂度,但能有效地减少Dijkstra算法的调用次数;与深度优先搜索、几何代数算法相比,分层Dijkstra算法虽然不一定能找到理论最优解,但出解速度较快,在数据量较大的情况下能快速找到次优解.

路由算法;最短路径;节点约束型;回溯法;贪心算法

最短路径问题[1]是图论中的经典问题,在现有研究中最短路径问题大概分为单对节点间最短路径、单个节点对所有节点间最短路径、K最短路径、实时最短路径、过指定必经节点/节点集的最短路径(节点约束型最短路径).此外,最短路径问题又可衍生出其他一些特殊的最短路径问题,如限制弧段数的最短路径、含环路路径等,此处不赘述.

文中主要研究节点约束型最短路径问题,该类问题比单纯的最短路径问题更具有实际意义和应用价值,主要应用于以下4个方面:

(1)旅行商问题[2-3].给旅行家设计一条旅行线路,使得他从某地出发,途经一些计划的旅游景点后,到达另一目的地的总距离最短.

(2)路由规划问题[4-5].设计若干路由之间的连接方法,使该规划能经过预定的重要路由基站,而且路径不能成环,同时使路径成本尽可能低.

(3)公交车线路问题.设计一条公交车线路,使得公交车能在最短的时间内经过某些较重要的站点.

(4)路网规划与导航问题[6].设计汽车在路网中的行驶路线,使得汽车能经过或避开某些指定地点,同时考虑费用、时间等约束.

以上问题在数据量较小的情况下可以通过遍历的方法穷举以筛选出最优的结果,但穷举这类问题时,随着数据量的增加,运算量也会快速的飙升,使得穷举方法在很多时候不能快速地找到次优解或可行解,而且花费的时间资源较大.因此如何求解此类问题的最优解或次优解,依然存在较大的研究价值.

Dijkstra算法[7]是解决单个节点到所有节点问题的经典算法,Dijkstra算法具有时间复杂度低、运算效率高等优点.但Dijkstra算法无法有效地求解上述问题,因此,文中以Dijkstra算法为基础,通过构建多层的回溯结构,以有向有权图为例,提出了一种新的解决方案,并给出了其关键部分的算法流程.

1 相关研究

最短路径问题一直是一个受到广泛关注的问题,针对这类问题,Dijkstra于1959年提出了一种经典的最短路径算法[7],该算法有效地解决了单个节点到其他节点间的最短路径问题和单对节点间的最短路径问题,但Dijkstra算法无法解决类似节点约束型的最短路径问题.随着对该算法研究的深入,出现了许多对Dijkstra算法的进一步优化方法和实际应用方案[8-10].与此同时,人们也开始引入许多智能算法(如蚁群算法、遗传算法、遗传禁忌搜索[11]、模拟退火[12]等)对最短路径问题进行求解,出现了采用神经网络[13]、自适应视野的人工鱼群算法[14]等求解最短路径的解决方案.通过对现有文献的分析与梳理,针对节点约束型最短路径问题的求解方法大致有以下几种:

(1)节点约束型最短路径的几何代数算法[15].该算法利用几何代数对网络进行表达与计算,利用矩阵的几何外积算法实现路径连接,通过有效的矩阵更新策略寻找可行的路径.该算法理论上能解出一定约束条件下的最优解,而且耗时比穷举方法少,但当数据量增加到一定程度时,该算法可能无法在短时间内得到可行解.

(2)基于Dijkstra和贪心算法的过指定节点的最短路径算法[16].该算法通过穷举所有指定节点的排列组合,再依次利用Dijkstra算法连接所有指定节点.该算法在中间节点较少时适用性较好,但由于算法中需要对所有中间节点的排列顺序依次进行尝试,随着中间节点的增加,运算所需时间会以阶乘级递增.因此,当必经节点较多时,可能无法快速找到可行解.

(3)利用遗传算法对必经节点最短路径问题求解的算法[17].该算法利用遗传算法,通过在不同的约束条件下寻找合适的适应度函数,使种群向预定的方向选择、交叉与变异,最终趋向于目标解.该算法只要对特定的条件设计出相应的适应度函数,便可以快速有效地求出最优解或次优解,而且解的收敛性较为理想.但此算法的适应度函数的设计与实现较为困难,而且只要对问题的条件稍作改变便需要重新设计适应度函数,使得该算法的灵活性受到一定的限制.

2 问题定义

给定一个带权重的有向图G=(V,E),V为节点集,E为有向边集,每一条有向边均有一个权重.对于给定的节点s、e及V的子集V′,寻找从s到e的不成环有向路径P,使得P经过V′中所有的节点(对经过V′中节点的顺序不做要求).

下面首先对一些相关概念进行描述:

相关节点包括起点s、终点e和必经节点集V′中的所有节点.

一条有向边对应一个权值,权值可理解为这条边的距离或者走这条边所需的花费.某一路径的总权值即为该路径所经过的所有边的权值之和.

路径由若干条边首尾连接而成,一条路径中不存在一个节点连接到多条边或多条边连接到一个节点的结构,一个解即指一条路径.

一条以给定的节点s为起点、给定的节点e为终点、经过了节点集V′中的所有节点且不成环的路径为一条合法路径,也称为合法解.

成环是指在路径中存在某一段首尾相接的现象,即从某一点出发,走过若干节点后回到原来的节点,该段也称为回路.某一路径成环可以表达为该路径中存在回路.

在所有解中,所有边的权值总和最小的合法解称为最优解,即最优路径.

为了更加清晰地描述问题,文中以图1所示的有向图为例,若只需找A点到D点的最短路径,则路径A→C→D应该为最短路径,其总权值为2.但如果需要找从A点到D点的最短路径,且要求经过B、C两点,同时要求路径不能成环,则符合条件的应该有两条路径,分别为A→B→C→D和A→C→B→D.其中前者总权值为5,小于后者,因此路径A→B→C→D为本例的最优解.

图1 有向有权图示例

3 分层Dijkstra算法设计与实现

3.1 Dijkstra算法和回溯结构

3.1.1 Dijkstra算法

Dijkstra算法[7]是针对单源最短路径问题的经典算法,该算法用于计算从一个节点出发到其他所有节点的最短路径.其基本思路是以起点开始向外层扩展,直到扩展到终点或所有点为止.Dijkstra算法求解最短路径问题的基本步骤如下:

(1)设立用于保存所有等待访问的节点集合T和记录所有已经访问过的节点集合S.集合T初始化为只有起始节点,集合S初始化为∅.

(2)从集合T中找出距离起始节点最近的节点,放入集合S中.

(3)更新与该节点直接相连的所有节点到起始节点的最短距离,这一步称为松弛操作,同时把这些相邻节点加入集合T中.

(4)返回步骤(2)直到集合T为∅则立即停止算法,此时,集合S中包含了网络中从起始节点出发可以到达的所有节点.

3.1.2 回溯结构

回溯法是一种遍历的方法,主要思想是在包含问题所有解的解空间树中,利用深度优先搜索策略,从根节点出发探索解的空间树.当探索到某一节点时,先判断该节点是否包含问题的解,如果包含,就继续探索下去,否则逐层向其祖先节点回溯,直到找到目标解或遍历所有解.当路径的深度搜索过程遇到无法继续向前寻找路径时,返回其祖先节点以实现所有路径的遍历.文中所说的回溯结构是指利用回溯法的主要思想设计的一种求解思路.

3.2 分层Dijkstra算法

借鉴回溯法的总体思路,文中提出了一种针对节点约束型最短路径的分层Dijkstra算法,其核心思想是将回溯法以及分层结构融入Dijkstra算法来寻找最优路径.为了便于描述,文中结合图2对算法进行阐述.假设有m个必经节点,那么在算法初始化时需要开辟一个m+1层的空间,每一层有独立的资源,互不干扰.从第0层即初始层开始,用Dijkstra算法从该层的起始节点向外扩展,如图中步骤①.当扩展到某一个必经节点时,保留当前层的扩展进度,转到下一层,如图中步骤②,同时继续以找到的必经节点为下一层的起始节点(步骤③),继续利用Dijkstra算法寻找路径.当发现从第n-1层进入第n层后,若在第n层无法找到下一个节点,则返回到第n-1层(步骤⑤),继续第n-1层的扩展进度(步骤⑥),直到遇到下一个必经节点,再按照正常的流程继续寻找路径.因为每次都是遇到必经节点就转入下一层,因此,如果在第m层到达终点e,则表示已找到一条合法路径.

图2 分层Dijkstra算法示意图

在上述描述的基础上,文中绘制了分层Dijkstra算法流程图,如图3所示.

图3 分层Dijkstra算法流程图

为了更清晰地阐释本算法的总体流程,文中以图1所示的有向有权图为例说明文中算法的计算过程.即通过文中算法求解如图1所示的有向有权图中,从A点出发到D点结束,而且经过B、C两点(对必经节点的先后顺序无要求)的最短路径问题,具体步骤如下:

(1)在第0层以A为起始节点,用Dijkstra算法找到节点C(C为必经点),转到下一层.

(2)在第1层以C为起始节点,找到节点B,转到下一层.

(3)在第2层以B为起始节点,找到终点D,为可行路径,权值为6.因为当前层无其他路径,返回上一层.

(4)在第1层从步骤(2)的进度继续,找到终点D,但未经过所有必经节点,放弃该点.因为已搜索所有节点,故返回上一层.

(5)在第0层从步骤(1)的进度继续,找到节点B,转到下一层.

(6)以同样方法往下两层找到节点C、D,判断为可行路径,权值为5.

(7)逐层返回到第0层,无可行路径,退出算法.

3.3 算法优化策略

在算法的具体实现过程中还需要采用一些有效的策略以提高算法的求解效率,如采用无回路控制策略以确保找到的解为合法解,采用一定的剪枝策略以提高路径寻找的速度,以及路径的记录方式等.

3.3.1 无回路控制策略

按照前述的问题描述,所求得的最终路径不能成环,而成环必将出现某一节点经过两次的情况,因此无回路条件只需保证任何节点最多只经过一次即可.文中假设当前路径已经过的节点集合为Vp,则在利用Dijkstra算法更新节点距离时,首先判断该点是否在集合Vp中,若在集合Vp中,则不对该点进行距离的更新,并使该点距离保持为无穷大,即使得该点处于不可到达的状态.

3.3.2 遍历策略

若需要保证搜索过程中能够遍历所有必经节点的排列组合,则搜索的范围应该包含所有可能.若通过Dijkstra算法在两相关节点A、B间找到的最短路径经过了另外一个相关节点C,且不加其他限制,则C点在A点之前和C点在B点之后的排列会被排除,从而无法真正遍历到所有可能的解,因此需要使用和3.3.1节中提到的类似方法更新相关节点的距离,以确保一层的两个相关节点间不会经过其他的相关节点.

3.3.3 剪枝策略

剪枝是对某些不可能出现或以很小概率出现合法路径或更优路径的情况进行删除的操作,以避免无意义的运算,缩短求解时间.因此,文中有针对性地提出了两种剪枝策略:①在寻找路径的过程中,若还未达到终点,但目前累计的权值已经超过了曾经找到的某一条合法路径的总权值,那么即使当前的路径继续延伸能达到终点并形成合法解,当前路径也不可能出现更优解,应当放弃并回溯到其父节点;②若在寻找路径过程中到达某一节点A时,存在一个未经过的相关节点B,使得没有任何路径可以从节点A出发到达节点B,则表明当前节点A与相关节点B不连通,可预见以后必定存在相关节点B无法到达,因此当前路径不包含合法解,应当及时删除.在实际应用中可以在图3所示流程图的“本层初始化”时加入连通性检查,以及时排除不含可行解的路径.

3.3.4 路径的记录方式

单纯利用Dijkstra算法只能算出起始节点到其他所有节点的距离,但在求解最短路径问题时不仅需要知道路径的总距离,还需要知道这条路径具体的节点序列.因此在对所有节点进行距离更新时,文中实时记录下每一个被更新节点对应的上一个节点ID值.查看路径时只需要依次查找上一个节点,直到起始节点即可获得该路径的节点序列.

分层结构下的路径记录与上述方法类似,在一层中利用这个方法记录路径,当跳入下一层时,将该层的路径读出来并整合到另一个记录路径的容器中,若出现回溯的返回操作,则将相应的路径段删除便可实现分层结构下的路径记录.

4 算法性能分析与比较

为了说明文中算法的有效性,文中设计了两组实验,一组实验是采用文中算法与未利用分层结构的Dijkstra算法[16]进行比较,以说明文中算法的分层结构在提高计算效率方面的有效性;另一组实验是文中算法与现有几种过必经节点最短路径算法进行可行解优劣和求解耗时上的综合性能比较,以说明文中算法的有效性.

4.1 分层结构的有效性分析

文献[16]是对所有必经点全排列后再依次使用Dijkstra算法,假设图中共有n个节点,其中有m个为必经节点,则必经节点全排列有m!种情况,每条路径共划分为m+1段,每段都需要调用一次Dijkstra算法,因此Dijkstra算法被调用(m+1)!次.而文中因为利用分层结构来保存进度的方法,虽然增加了一定的空间复杂度,但能较大幅度地减少Dijkstra算法的调用次数.为了便于说明,文中先用图1所示有向图进行简要说明,并分析文献[16]和文中算法调用Dijkstra算法的次数.图1所示有向有权图包含2个必经节点,按文献[16]算法先将全部必经节点全排列,则一共有两种排列,每条路径包含4个相关节点,分为3段,每段需要调用一次Dijkstra算法,因此共调用了6次.而按照文中算法,有2个必经点,初始化时开辟3层的空间,从第0层A点出发调用了一次,从第1层B点、C点出发各调用一次,从第2层对应C点、B点出发到终点再各调用一次,一共调用5次,调用次数比文献[16]算法少.而随着中间节点数的增加,两种算法的调用次数差距会越来越大,虽然具体调用次数表达式无法实际算出,但通过递推关系可计算出中间节点数为1到20时分层结构Dijkstra算法的调用次数,并与文献[16]算法的调用次数进行对比,结果如图4所示,为了便于对比观察,图中的纵坐标采用等立方根间距坐标表示,当中间节点数增加至20时,文中算法对Dijkstra算法的调用次数仅约为文献[16]算法的1/7,当中间节点数增加至50时,文中算法的调用次数仅为文献[16]算法的1/18,由此可见分层结构在提高计算效率方面的有效性.

图4 两种算法调用Dijkstra算法的次数

4.2 算法整体效果对比

采用深度优先搜索法[18]、几何代数法[15]及文中分层Dijkstra算法进行实验比较.其中,深度优先搜索法增加了针对节点约束型最短路径问题的剪枝操作,本实验的几何代数法则在文献[15]算法的基础上进行了改进,将针对无向无权图的求解方法修改至可应用于有向有权图,并增加了一定的剪枝操作.为了增加实验的可信度,文中实验数据采用随机生成的若干规模样例,已确认样例均有解而且3种算法的解均为合法解,等待30 s若未结束则作为超时处理,实验结果如表1所示.从表中可知,几何代数法第1个解的质量普遍较优,而且几何代数法出解数量较少,一般只会解出1到2个解,但其求解时间很长.分层Dijkstra算法虽然第1个解的质量不如几何代数法,但出解时间远小于几何代数法,而且在必经节点规模较大时依然能快速地找到一个合法解,也能在短时间内收敛到一个次优解.

表1 3种算法的实验结果对比

规模为50个节点(其中包含10个必经节点)时3种算法的权值-时间曲线如图5所示,为便于比较,横轴采用对数坐标表示.从图中可以看出:对于本样例,几何代数法只求出一个解,解出的权值较小;深度优先搜索法求出的解最多,但解的收敛性相对较差;文中分层Dijkstra算法的出解速度与收敛性最为理想.

图5 3种算法的求解时间与权值比较

Fig.5 Comparison of solution time and weights of three algorithms

5 结论

文中利用Dijkstra算法作为寻找路径的基础,结合回溯结构,针对节点约束型最短路径问题设计了新的分层Dijkstra算法.实验结果表明:分层Dijkstra算法虽然不一定能找到理论最优解,但在时间复杂度上有一定的优势,出解速度较快;通过设计不同的延伸策略可以使该算法能很好地应用于回路、必经节点等的判断与剪枝;该算法即使在数据量较大的情况下依然能快速找到次优解.虽然文中算法是针对有向有权图进行设计的,但只需简单修改即可应用于无向图或无权图.由于文中的分层Dijkstra算法是利用回溯结构实现的,因此对其进行剪枝等操作时会更加方便,可用于邮递员问题、旅行商问题及其他类似问题的求解.

[1] 陆锋.最短路径算法:分类体系与研究进展 [J].测绘学报,2001,30(3):269- 275.

LU Feng.Shortest path algorithms:taxonomy and advance in research [J].Acta Geodaetica et Cartographica Sinica, 2001,30(3):269- 275.

[2] 吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法 [J].计算机学报,2001,30(12):1328-1333.

WU Bin,SHI Zhong-zhi.An ant colony algorithm based partition algorithm for TSP [J].Chinese Journal of Computers,2001,30(12):1328-1333.

[3] 刘锦.混合遗传算法和模拟退火算法在TSP中的应用研究 [D].广州:华南理工大学,2014.

[4] 孙雨耕,胡华东,杨挺.一种应用于路由规划的实用无环K路算法 [J].计算机工程,2003,29(22):128-130.

SUN Yu-geng,HU Hua-dong,YANG Ting.A practical loop-lessK-path algorithm applied in route planning [J]. Computer Engineering,2003,29(22):128-130.

[5] 曲大鹏,王兴伟,黄敏.移动对等网络中的感知蚁群路由算法 [J].计算机学报,2013,36(7):1456-1464.

QU Da-peng,WANG Xing-wei,HUANG Min.An aware ant routing algorithm in mobile peer-to-peer networks [J]. Chinese Journal of Computers,2013,36(7):1456-1464.

[6] 赵艳丽.实际路网最短路径算法优化与实现 [D].广州:华南理工大学,2015.

[7] DIJKSTRA E W.A note on two problems in connexion with graphs [J].Numerische Mathematik,1959,1:269- 271.

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

WANG Shu-xi,WU Zheng-xue.Improved Dijkstra shortest path algorithm and its application [J].Computer Science,2012,39(5):223- 228.

[9] 王华.改进Dijkstra算法的城市道路最短路径仿真研究 [J].测绘科学,2013,38(4):149-151.

WANG Hua.Improved Dijkstra algorithm for shortest path in urban traffic net [J].Science of Surveying and Mapping,2013,38(4):149-151.

[10] 王树西,李安渝.Dijkstra算法中的多邻接点与多条最短路径问题 [J].计算机科学,2014,41(6):217- 224.

WANG Shu-xi,LI An-yu.Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm [J]. Computer Science,2014,41(6):217- 224.

[11] 余丽,陆锋,杨林.交通网络旅行商路径优化的遗传禁忌搜索算法 [J].测绘学报,2014,43(11):1197-1203.

YU Li,LU Feng,YANG Lin.A hybrid algorithm for tra-veling salesman problem in road network [J].Acta Geodaetica et Cartographica Sinica,2014,43(11):1197- 1203.

[12] 黄樟灿,陈思多,康立山,等.基于模拟退火算法的曲面最短路径求解 [J].武汉大学学报(自然科学版), 2000,46(3):273- 276.

HUANG Zhang-can,CHEN Si-duo,KANG Li-shan,et al. Solving the shortest path on curved surface based on si-mulated annealing algorithm [J].Journal of Wuhan University(Natural Science Edition),2000,46(3):273- 276.

[13] 陈华志,谢存禧,曾德怀.基于神经网络的移动机器人路径规划算法的仿真 [J].华南理工大学学报(自然科学版),2003,31(6):56-59.

CHEN Hua-zhi,XIE Cun-xi,ZENG De-huai.Simulation of a neural network-based path planning algorithm for mobile robot [J].Journal of South China University of Technology(Natural Science Edition),2003,31(6):56-59.

[14] 马宪民,刘妮.自适应视野的人工鱼群算法求解最短路径问题 [J].通信学报,2014,35(1):1- 6.

MA Xian-min,LIU Ni.Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem [J].Journal on Communications,2014,35(1):1- 6.

[15] 冯琳耀,袁林旺,罗文,等.节点约束型最短路径的几何代数算法 [J].电子学报,2014,42(5):846- 851.

FENG Lin-yao,YUAN Lin-wang,LUO Wen,et al.Geometric algebra-based algorithm for solving nodes constrained shortest path [J].Acta Electronica Sinica,2014,42(5):846- 851.

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

HUANG Shu-li,HU Da-sha,JIANG Yu-ming.Algorithm for finding shortest path which must go through specified intermediate node set [J].Computer Engineering and Applications,2015,51(11):41- 46.

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

XU Qing-zheng,KE Xi-zheng.Models and genetic algorithm for designated-points shortest path problem [J]. Systems Engineering and Electronics,2009,31(2):459- 462.

[18] 房佳,杜震洪,张丰,等.应用于城市道路网的启发式深度优先有向搜索算法 [J].浙江大学学报(理学版),2013,40(4):469- 474.

FANG Jia,DU Zhen-hong,ZHANG Feng,et al.Heuristic depth-first directional algorithm for shortest path sear-ching in traffic networks [J].Journal of Zhejiang Univer-sity(Science Edition),2013,40(4):469- 474.

A Hierarchical Dijkstra Algorithm for Solving Shortest Path from Constrained Nodes

KANGWen-xiongXUYao-zhao

(School of Automation Science and Engineering, South China University of Technology, Guangzhou 510640, Guangdong, China)

In order to obtain the shortest path from constrained nodes, a hierarchical Dijkstra algorithm is proposed on the basis of backtracking, which is able to find the global shortest path or the second shortest path by searching the local optimal solution within hierarchical structures. Moreover, this algorithm takes full advantage of the hierarchical structures in saving search progress to realize such operations as the saving and backtracking of the search progress during the searching of the shortest path. Experimental results show that the proposed algorithm increases space complexity slightly, but it can reduce the calls of Dijkstra algorithm effectively, and that, as compared with depth-first search algorithm and geometric algebra algorithm, the proposed algorithm may not always find the optimal solution in theory, but it works faster and can still find the sub-optimal solution more quickly even when data volume is large.

routing algorithms; shortest path; node constraint; backtracking; greedy algorithm

1000-565X(2017)01- 0066- 08

2016- 06-20

国家自然科学基金资助项目(61573151,61105019);广东省自然科学基金资助项目(2016A030313468)

Foundation items： Supported by the National Natural Science Foundation of China(61573151,61105019) and the Natural Science Foundation of Guangdong Province(2016A030313468)

康文雄(1976-),男,博士,副教授,主要从事计算机视觉及生物特征识别研究.E-mail:auwxkang@scut.edu.cn

TP 301.6

10.3969/j.issn.1000-565X.2017.01.010