基于极小代数赋权有向图最短路径求解算法

李彦平, 魏　昆, 王　丹, 谭清化

(沈阳大学 a. 辽宁省装备制造综合自动化重点实验室, b. 信息工程学院, 辽宁 沈阳　110044)



基于极小代数赋权有向图最短路径求解算法

李彦平a,b, 魏昆a, 王丹a, 谭清化b

(沈阳大学 a. 辽宁省装备制造综合自动化重点实验室, b. 信息工程学院, 辽宁 沈阳110044)

摘要:应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法. 该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Aspan和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径. 与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.

关键词:极小代数; 赋权有向图; 距离矩阵; 路径规划; 最短路径

路径规划问题在物流管理、城市规划和工厂布局等方面发挥着越来越重要的作用[1]. 所谓路径规划问题,就是指按照某种规则寻找一条从起始点到终点的有效路径或最短路径. 求解最短路径具有非常广泛的应用领域[2-4]. 最短路径通常是指距离最短,但有时从广义上也可以是时间最短、消耗资源最少等.

计算最短路径常用的方法有求解非负权边的单向最短路径的Bellman-Ford算法[5]、解决有向图中单个节点分别到其他各个顶点的最短路径问题的迪科斯彻算法( Dijkstra’s algorithm)[6]、求解每对顶点之间最短距离的Floyd-Warshall算法[7]以及求解每对顶点间的最短路径的Johnson算法[8]等. 目前所使用的最基本的和最广泛的算法,是由F W Dijkstra提出的Dijkstra算法[9]. 许多文献也讨论了该算法的实现方法以及改进方法,但作为最短路径问题的关键环节,其计算过程过于复杂,数据存储过于庞大,直接影响了算法的计算速度. 因此,提高算法效率以及提出运算效率更高的新算法成为研究最短路径问题的热点.

在研究最短路径问题时,通常将运行环境抽象成图论下的赋权网络模型,根据赋权网络模型求解最短路径及最短路径长度. 本文应用极小代数给出求解简单有向赋权图最短路径问题的代数算法. 该算法通过赋权有向图直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵(k幂矩阵)Ak和最短路径距离矩阵A+,并依此确定赋权有向图的最短路径以及最少步数最短路径. 基于极小代数求解最短路径,能够使问题更加清晰,逻辑性较强,算法运算过程具有数据存储量小、计算复杂度小的优点.

1最短路径问题的提出

在路径规划问题中,通常将所处运行环境抽象成赋权有向图模型,运行环境中,道路之间的交叉点可以用图中的节点表示,而道路本身可以用图中的边表示. 在路径规划问题中,有向图模型的边往往是被赋权的,表示两节点之间的路径长度或从一个节点到达相邻另一节点所耗费的时间、成本等.路径规划问题的一种评价标准是求得最短路径. 本文提出了一种基于极小代数的路径规划算法,通过该算法寻求一条最短路径.

定义3对于一个简单赋权有向图G=(V,E,a), 称节点i到j之间存在一条k步路径(点表达):

(1)

对于赋权有向图,可以在图中的两点之间寻找一条k步最短路径或一条最短路径或一条最少步数最短路径.

定义4称路径lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k))为一条由节点i到节点j的k步最短路径,如果(v(0),v(1),…,v(k))是如下路径规划问题的解:

(2)

式中,v(s)∈V,1≤s≤k.

定义5称路径lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k))为一条由节点i到j的最短路径,如果(k,v(0),v(1),…,v(k))是如下路径规划问题的解:

(3)

式中,v(s)∈V,1≤s≤k,1≤k≤n.

对于简单赋权有向图G=(V,E,a),由映射a可以生成关于图的直接距离矩阵A=(a(i,j))n×n,其中,a(i,j)≠ε表示节点i到j间直接连通,a(i,j)=ε则表示节点i与j之间不直接连通. 在极小代数意义下,对直接距离矩阵定义以下运算.

(1) ⊕运算(“加法”):∀A,B∈Dn×m,则

式中,A=(a(i,j))n×m,B=(b(i,j))n×m,C=(c(i,j))n×m,c(i,j)=a(i,j)⊕b(i,j).

(2) ⊗运算(“乘法”):∀A∈Dn×m,B∈Dm×s,则

(3) 幂运算:∀A∈Dn×n, 则

(4) A+运算:

式中,A,A2,…,An,A+∈Dn×n,A=(a(i,j))n×n,A2=(a2(i,j))n×n,…,An=(an(i,j))n×n, A+=(a+(i,j))n×n,a+(i,j)=a(i,j)⊕a2(i,j)⊕…⊕an(i,j).

矩阵Ak中元素ak(i,j)为由节点i到j的k步最短路径的长度,矩阵A+中元素a+(i,j)为节点i到节点j的最短路径的长度. 若(v(0),v(1),v(2),…,v(k-1),v(k))为一条由节点i到j的k步最短路径,则有d(lk(i,j))=ak(i,j);若其为一条由节点i到节点j的最短路径,则有d(lk(i,j))=a+(i,j).

在一个赋权有向图中,k步最短路径和最短路径都可能是不唯一的,且最短路径的步数也有可能是不唯一的. 为此,可以定义一个最少步数最短路径.

定义6称路径lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k))为一条由节点i到j的最少步数最短路径,如果d(lk(i,j))=a+(i,j), 并且

(4)

2最短路径求解算法

综上可知,由节点i到j的最少步数最短路径长度为a+(i,j),可通过极小代数意义下矩阵的幂运算来确定该最短路径中所包含的所有节点. 假设该最少步数最短路径为k步,这条k步路径为lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k)),其中,v(0)=i为路径的起点,v(k)=j为路径的终点.k步最短路径lk(i,j)求解算法的具体步骤如下.

(1) 构建关于图的直接距离矩阵A,计算矩阵A2,A3,…,An,其中,n为简单赋权有向图中节点的个数.计算A+=A⊕A2⊕A3⊕…⊕An.

(2) 输入路径的起点i和终点j.

(4) 赋值v(0)=i,v(k)=j,s=k.

(5) 判断s-1是否为0.若s-1≠0,则选择v(s-1)∈{q:as(i,v(s))=as-1(i,q)⊗a(q,v(s))},赋值计算s=s-1,重复步骤(5).否则,输出结果lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k)).计算结束.

基于极小代数最少步数最短路径计算流程如图1所示.

图1　最少步数最短路径算法流程图

3算法实例分析

对于赋权(无向)图G′,因为沿边[i,j]既可以从节点i到达j,也可以从节点j到达i,所以弧[i,j]可以看作赋权有向图中的两条弧(i,j)和(j,i),它们具有相同的权函数w[i,j]. 这样,一个赋权(无向)图就可以看作一个边为双向的赋权有向图.

以图2所示的网络模型表示运行环境,用如下实例来说明本文所提出的代数算法的有效性及正确性.运输机械在图2上的运行路径起点为节点1,终点为节点4,则该运行路径表示为lk(i,j)=(1,4),并且v(0)=1,v(k)=4.下面求解该路径的最少步数最短路径长度以及所经过的中间节点.

图2　图论模型

求解该路径的最少步数最短路径长度以及所经过的中间节点的代数算法的具体步骤如下.

(1) 由图2得到的直接距离矩阵A为

(2) 通过直接距离矩阵A计算得到矩阵A2,A3,…,An,并计算A+=A⊕A2⊕A3⊕…⊕An:

(3) 从最短路径长度矩阵A+中找到元素a+(1,4)=20≠ε,可知路径lk(i,j)存在一条最少步数最短路径并且最短路径长度是20.

(4) 在矩阵A3中能够看到a3(1,4)=a+(1,4),则有k=3,即该路径的最少步数为3,并且v(0)=1,v(k)=v(3)=4.记s=3.

(5) 因为s-1>0,所以v(3-1)∈{q:a3(1,4)=a2(1,q)⊗a(q,4)},得到满足集合q的元素有a2(1,3)和a2(1,5),随机地取a2(1,3)为满足集合的元素,此时,v(s-1)=v(2)=q=3,记录节点v(2)=3,s=s-1,s=2.

(6) 因为s-1>0,所以v(2-1)∈{q:a2(1,3)=a(1,q)⊗a(q,3)},得到满足集合q的元素a(1,2),此时,v(s-1)=v(1)=q=2,记录节点v(1)=2,s=s-1,s=1.

(7) 此时s-1=0,所以由代数算法得到的最少步数最短路径l3(i,j)=(v(0),v(1),v(2),v(3))=(1,2,3,4,),最短路径长度为d(l3(1,4))=20. 算法结束.

4与Dijkstra算法的计算复杂度的对比

Dijkstra算法[10]是目前求解最短路径问题最流行的算法之一. 该算法要遍历从每一节点出发的所有节点, 最终生成的不仅是起点到终点的最短路径, 而且还要求出起点到图中其他所有节点的最短路径. 由于传统的Dijkstra算法使用的是线性数组结构,因此,每次操作都要遍历整个节点列表, 即顺序遍历整个最短路径树,其整个算法的运行时间为o(n2)[11]. 而本文所提出的算法在得到直接距离矩阵A以及最短路径距离矩阵A+后,所要计算的是从路径终点到路径起点经过的中间节点,不需要计算终点到其他节点的路径长度,故该算法的效率大大提高,整个算法的运行时间为o(n). 所以本文所提出的算法较传统的Dijkstra算法的运算效率要高.

5结语

基于极小代数所提出的求解最短路径代数算法通过赋权有向图的直接距离矩阵A,计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,依次求解赋权有向图的最短路径以及最少步数最短路径,并且应用实例验证了算法的正确性及有效性.本文所提出的代数算法与传统的基于网络分析的求解最短路径方法相比更加规范、系统,逻辑性强,并且思路清晰. 从代数的角度观察、分析路径规划问题,能够更加容易看清问题的本质,算法比较容易建立、分析和实现.

参考文献:

[ 1 ] 甘应爱,田丰,钱颂迪. 运筹学[M]. 北京: 清华大学出版社, 2011:251-255.

(Gan Ying’ai,Tian Feng,Qian Songdi. Operations Research[M]. Beijing: Tsinghua University Press, 2011:251-255.)

[ 2 ]CherkasskyBV,GoldbergAV,RadzikT.ShortestPathsAlgorithms:TheoryandExperimentalEvaluation[J].MathematicalProgramming, 1996,73(2):129-174.

[ 3 ]LuFeng,ZhouChenghu,WanQing.AnOptimumVehicularPathAlgorithmforTrafficNetworkBasedonHierarchicalSpatialReasoning[J].Geo-spatialInformationScience, 2000,3(4):36-42.

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

(LuFeng.ShortestPathAlgorithms:TaxonomyandAdvanceinResearch[J].ActaGeodaeticaetCartographicaSinica, 2001,30(3):269-275.)

[ 5 ] 宫恩超,李鲁群. 基于Bellman-Ford算法的动态最优路径算法设计[J]. 测绘通报, 2011(8):26-28,41.

(GongEnchao,LiLuqun.TheOptimalPathAlgorithmDesignBasedonBellman-FordAlgorithm[J].BulletinofSurveyingandMapping, 2011(8):26-28,41.)

[ 6 ] 鲍培明. 距离寻优中Dijkstra算法的优化[J]. 计算机研究与发展, 2001,38(3):307-311.

(BaoPeiming.AOptimizationAlgorithmBasedonDijkstra’sAlgorithminSearchofShortcut[J].JournalofComputerResearchandDevelopment, 2001,38(3):307-311.)

[ 7 ]HöfnerP,MöllerB.Dijkstra,FloydandWarshallMeetKleene[J].FormalAspectsofComputing, 2012,24(4/5/6):459-476.

[ 8 ] 王银燕,余镇危,曹怀虎,等. 基于二度量的单播最短路径算法[J]. 计算机工程, 2007,33(5):89-90.

(WangYinyan,YuZhenwei,CaoHuaihu,etal.AlgorithmforTwo-MetricUnicastShortestPath[J].ComputerEngineering, 2007,33(5):89-90.)

[ 9 ] 王志和,凌云.Dijkstra最短路径算法的优化及其实现[J]. 微计算机信息, 2007,23(33):275-277.

(WangZhihe,LingYun.TheOptimizationandImplementationoftheShortestPathDijkstraAlgorithm[J].MicrocomputerInformation, 2007,23(33):275-277.)

[10] 卢香清,李洪安,康宝生,等. 图最短路径并行化机器应用研究[J]. 计算机工程与应用, 2012,48(14):38-43.

(LuXiangqing,LiHongan,KangBaosheng,etal.ResearchonParallelizationofShortestPathforGraphanditsApplication[J].ComputerEngineeringandApplications, 2012,48(14):38-43.)

[11] 李元臣,刘维群. 基于Dijkstra算法的网络最短路径分析[J]. 微计算机应用, 2004,25(3):295-298.

【责任编辑: 李艳】

(LiYuanchen,LiuWeiqun.AnalysisoftheShortestRouteinNetWorkonDijkstraAlgorithm[J].MicrocomputerApplications, 2004,25(3):295-298.)

An Efficient Algorithm for Solving Shortest Path of Weighted Digraph Based on Min-algebra

LiYanpinga,b,WeiKuna,WangDana,TanQinghuab

(a. Key Laboratory of Manufacturing Industrial Integrated Automation, b. School of Information Engineering, Shenyang University, Shenyang 110044, China)

Abstract:An efficient algorithm based on min-algebra is developed for solving the shortest path problem in a simple weighted directed graph. This algorithm calculates shortest path matrix Aspanofksteps (kexponential matrix) and shortest path matrix A+with min-algebra by the direct distance matrix A of directed graph. Accordingly, the shortest path and the shortest path of minimal steps in the directed graph can be determined. The certain shortest path and its length are obtained by the proposed algorithm faster than Dijkstra algorithm.

Key words:min-algebra; weighted digraph; distance matrix; path planning; shortest path

收稿日期:2014-06-26

中图分类号:TP 301.6

文献标志码:A

作者简介:李彦平(1957-),男,辽宁锦州人,沈阳大学教授,博士.

基金项目:国家自然科学基金青年科学基金资助项目(61203152); 辽宁省博士科研启动基金资助项目(20121040).

文章编号:2095-5456(2015)01-0025-05