李彥平, 魏　昆, 王　丹, 譚清化

(沈陽(yáng)大學(xué) a. 遼寧省裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, b. 信息工程學(xué)院, 遼寧 沈陽(yáng)　110044)

?

基于極小代數(shù)賦權(quán)有向圖最短路徑求解算法

李彥平a,b, 魏昆a, 王丹a, 譚清化b

(沈陽(yáng)大學(xué) a. 遼寧省裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, b. 信息工程學(xué)院, 遼寧 沈陽(yáng)110044)

摘要:應(yīng)用極小代數(shù)給出了求解簡(jiǎn)單有向賦權(quán)圖最短路徑問(wèn)題的代數(shù)算法. 該算法基于賦權(quán)有向圖的直接距離矩陣A,在極小代數(shù)意義下計(jì)算k步最短路徑距離矩陣Aspan和最短路徑距離矩陣A+,并依此確定出賦權(quán)有向圖的最短路徑以及最少步數(shù)最短路徑. 與Dijkstra算法相比較,所提出的代數(shù)算法求解路徑規(guī)劃問(wèn)題能夠較快地得到特定的最短路徑及其長(zhǎng)度.

關(guān)鍵詞:極小代數(shù); 賦權(quán)有向圖; 距離矩陣; 路徑規(guī)劃; 最短路徑

路徑規(guī)劃問(wèn)題在物流管理、城市規(guī)劃和工廠布局等方面發(fā)揮著越來(lái)越重要的作用[1]. 所謂路徑規(guī)劃問(wèn)題,就是指按照某種規(guī)則尋找一條從起始點(diǎn)到終點(diǎn)的有效路徑或最短路徑. 求解最短路徑具有非常廣泛的應(yīng)用領(lǐng)域[2-4]. 最短路徑通常是指距離最短,但有時(shí)從廣義上也可以是時(shí)間最短、消耗資源最少等.

計(jì)算最短路徑常用的方法有求解非負(fù)權(quán)邊的單向最短路徑的Bellman-Ford算法[5]、解決有向圖中單個(gè)節(jié)點(diǎn)分別到其他各個(gè)頂點(diǎn)的最短路徑問(wèn)題的迪科斯徹算法( Dijkstra’s algorithm)[6]、求解每對(duì)頂點(diǎn)之間最短距離的Floyd-Warshall算法[7]以及求解每對(duì)頂點(diǎn)間的最短路徑的Johnson算法[8]等. 目前所使用的最基本的和最廣泛的算法,是由F W Dijkstra提出的Dijkstra算法[9]. 許多文獻(xiàn)也討論了該算法的實(shí)現(xiàn)方法以及改進(jìn)方法,但作為最短路徑問(wèn)題的關(guān)鍵環(huán)節(jié),其計(jì)算過(guò)程過(guò)于復(fù)雜,數(shù)據(jù)存儲(chǔ)過(guò)于龐大,直接影響了算法的計(jì)算速度. 因此,提高算法效率以及提出運(yùn)算效率更高的新算法成為研究最短路徑問(wèn)題的熱點(diǎn).

在研究最短路徑問(wèn)題時(shí),通常將運(yùn)行環(huán)境抽象成圖論下的賦權(quán)網(wǎng)絡(luò)模型,根據(jù)賦權(quán)網(wǎng)絡(luò)模型求解最短路徑及最短路徑長(zhǎng)度. 本文應(yīng)用極小代數(shù)給出求解簡(jiǎn)單有向賦權(quán)圖最短路徑問(wèn)題的代數(shù)算法. 該算法通過(guò)賦權(quán)有向圖直接距離矩陣A,在極小代數(shù)意義下計(jì)算k步最短路徑距離矩陣(k冪矩陣)Ak和最短路徑距離矩陣A+,并依此確定賦權(quán)有向圖的最短路徑以及最少步數(shù)最短路徑. 基于極小代數(shù)求解最短路徑,能夠使問(wèn)題更加清晰,邏輯性較強(qiáng),算法運(yùn)算過(guò)程具有數(shù)據(jù)存儲(chǔ)量小、計(jì)算復(fù)雜度小的優(yōu)點(diǎn).

1最短路徑問(wèn)題的提出

在路徑規(guī)劃問(wèn)題中,通常將所處運(yùn)行環(huán)境抽象成賦權(quán)有向圖模型,運(yùn)行環(huán)境中,道路之間的交叉點(diǎn)可以用圖中的節(jié)點(diǎn)表示,而道路本身可以用圖中的邊表示. 在路徑規(guī)劃問(wèn)題中,有向圖模型的邊往往是被賦權(quán)的,表示兩節(jié)點(diǎn)之間的路徑長(zhǎng)度或從一個(gè)節(jié)點(diǎn)到達(dá)相鄰另一節(jié)點(diǎn)所耗費(fèi)的時(shí)間、成本等.路徑規(guī)劃問(wèn)題的一種評(píng)價(jià)標(biāo)準(zhǔn)是求得最短路徑. 本文提出了一種基于極小代數(shù)的路徑規(guī)劃算法,通過(guò)該算法尋求一條最短路徑.

定義3對(duì)于一個(gè)簡(jiǎn)單賦權(quán)有向圖G=(V,E,a), 稱節(jié)點(diǎn)i到j(luò)之間存在一條k步路徑(點(diǎn)表達(dá)):

(1)

對(duì)于賦權(quán)有向圖,可以在圖中的兩點(diǎn)之間尋找一條k步最短路徑或一條最短路徑或一條最少步數(shù)最短路徑.

定義4稱路徑lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k))為一條由節(jié)點(diǎn)i到節(jié)點(diǎn)j的k步最短路徑,如果(v(0),v(1),…,v(k))是如下路徑規(guī)劃問(wèn)題的解:

(2)

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

定義5稱路徑lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k))為一條由節(jié)點(diǎn)i到j(luò)的最短路徑,如果(k,v(0),v(1),…,v(k))是如下路徑規(guī)劃問(wèn)題的解:

(3)

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

對(duì)于簡(jiǎn)單賦權(quán)有向圖G=(V,E,a),由映射a可以生成關(guān)于圖的直接距離矩陣A=(a(i,j))n×n,其中,a(i,j)≠ε表示節(jié)點(diǎn)i到j(luò)間直接連通,a(i,j)=ε則表示節(jié)點(diǎn)i與j之間不直接連通. 在極小代數(shù)意義下,對(duì)直接距離矩陣定義以下運(yùn)算.

(1) ⊕運(yùn)算(“加法”):?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) ?運(yùn)算(“乘法”):?A∈Dn×m,B∈Dm×s,則

(3) 冪運(yùn)算:?A∈Dn×n, 則

(4) A+運(yùn)算:

式中,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)為由節(jié)點(diǎn)i到j(luò)的k步最短路徑的長(zhǎng)度,矩陣A+中元素a+(i,j)為節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑的長(zhǎng)度. 若(v(0),v(1),v(2),…,v(k-1),v(k))為一條由節(jié)點(diǎn)i到j(luò)的k步最短路徑,則有d(lk(i,j))=ak(i,j);若其為一條由節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短路徑,則有d(lk(i,j))=a+(i,j).

在一個(gè)賦權(quán)有向圖中,k步最短路徑和最短路徑都可能是不唯一的,且最短路徑的步數(shù)也有可能是不唯一的. 為此,可以定義一個(gè)最少步數(shù)最短路徑.

定義6稱路徑lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k))為一條由節(jié)點(diǎn)i到j(luò)的最少步數(shù)最短路徑,如果d(lk(i,j))=a+(i,j), 并且

(4)

2最短路徑求解算法

綜上可知,由節(jié)點(diǎn)i到j(luò)的最少步數(shù)最短路徑長(zhǎng)度為a+(i,j),可通過(guò)極小代數(shù)意義下矩陣的冪運(yùn)算來(lái)確定該最短路徑中所包含的所有節(jié)點(diǎn). 假設(shè)該最少步數(shù)最短路徑為k步,這條k步路徑為lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k)),其中,v(0)=i為路徑的起點(diǎn),v(k)=j為路徑的終點(diǎn).k步最短路徑lk(i,j)求解算法的具體步驟如下.

(1) 構(gòu)建關(guān)于圖的直接距離矩陣A,計(jì)算矩陣A2,A3,…,An,其中,n為簡(jiǎn)單賦權(quán)有向圖中節(jié)點(diǎn)的個(gè)數(shù).計(jì)算A+=A⊕A2⊕A3⊕…⊕An.

(2) 輸入路徑的起點(diǎn)i和終點(diǎn)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))},賦值計(jì)算s=s-1,重復(fù)步驟(5).否則,輸出結(jié)果lk(i,j)=(v(0),v(1),v(2),…,v(k-1),v(k)).計(jì)算結(jié)束.

基于極小代數(shù)最少步數(shù)最短路徑計(jì)算流程如圖1所示.

圖1　最少步數(shù)最短路徑算法流程圖

3算法實(shí)例分析

對(duì)于賦權(quán)(無(wú)向)圖G′,因?yàn)檠剡匸i,j]既可以從節(jié)點(diǎn)i到達(dá)j,也可以從節(jié)點(diǎn)j到達(dá)i,所以弧[i,j]可以看作賦權(quán)有向圖中的兩條弧(i,j)和(j,i),它們具有相同的權(quán)函數(shù)w[i,j]. 這樣,一個(gè)賦權(quán)(無(wú)向)圖就可以看作一個(gè)邊為雙向的賦權(quán)有向圖.

以圖2所示的網(wǎng)絡(luò)模型表示運(yùn)行環(huán)境,用如下實(shí)例來(lái)說(shuō)明本文所提出的代數(shù)算法的有效性及正確性.運(yùn)輸機(jī)械在圖2上的運(yùn)行路徑起點(diǎn)為節(jié)點(diǎn)1,終點(diǎn)為節(jié)點(diǎn)4,則該運(yùn)行路徑表示為lk(i,j)=(1,4),并且v(0)=1,v(k)=4.下面求解該路徑的最少步數(shù)最短路徑長(zhǎng)度以及所經(jīng)過(guò)的中間節(jié)點(diǎn).

圖2　圖論模型

求解該路徑的最少步數(shù)最短路徑長(zhǎng)度以及所經(jīng)過(guò)的中間節(jié)點(diǎn)的代數(shù)算法的具體步驟如下.

(1) 由圖2得到的直接距離矩陣A為

(2) 通過(guò)直接距離矩陣A計(jì)算得到矩陣A2,A3,…,An,并計(jì)算A+=A⊕A2⊕A3⊕…⊕An:

(3) 從最短路徑長(zhǎng)度矩陣A+中找到元素a+(1,4)=20≠ε,可知路徑lk(i,j)存在一條最少步數(shù)最短路徑并且最短路徑長(zhǎng)度是20.

(4) 在矩陣A3中能夠看到a3(1,4)=a+(1,4),則有k=3,即該路徑的最少步數(shù)為3,并且v(0)=1,v(k)=v(3)=4.記s=3.

(5) 因?yàn)閟-1>0,所以v(3-1)∈{q:a3(1,4)=a2(1,q)?a(q,4)},得到滿足集合q的元素有a2(1,3)和a2(1,5),隨機(jī)地取a2(1,3)為滿足集合的元素,此時(shí),v(s-1)=v(2)=q=3,記錄節(jié)點(diǎn)v(2)=3,s=s-1,s=2.

(6) 因?yàn)閟-1>0,所以v(2-1)∈{q:a2(1,3)=a(1,q)?a(q,3)},得到滿足集合q的元素a(1,2),此時(shí),v(s-1)=v(1)=q=2,記錄節(jié)點(diǎn)v(1)=2,s=s-1,s=1.

(7) 此時(shí)s-1=0,所以由代數(shù)算法得到的最少步數(shù)最短路徑l3(i,j)=(v(0),v(1),v(2),v(3))=(1,2,3,4,),最短路徑長(zhǎng)度為d(l3(1,4))=20. 算法結(jié)束.

4與Dijkstra算法的計(jì)算復(fù)雜度的對(duì)比

Dijkstra算法[10]是目前求解最短路徑問(wèn)題最流行的算法之一. 該算法要遍歷從每一節(jié)點(diǎn)出發(fā)的所有節(jié)點(diǎn), 最終生成的不僅是起點(diǎn)到終點(diǎn)的最短路徑, 而且還要求出起點(diǎn)到圖中其他所有節(jié)點(diǎn)的最短路徑. 由于傳統(tǒng)的Dijkstra算法使用的是線性數(shù)組結(jié)構(gòu),因此,每次操作都要遍歷整個(gè)節(jié)點(diǎn)列表, 即順序遍歷整個(gè)最短路徑樹,其整個(gè)算法的運(yùn)行時(shí)間為o(n2)[11]. 而本文所提出的算法在得到直接距離矩陣A以及最短路徑距離矩陣A+后,所要計(jì)算的是從路徑終點(diǎn)到路徑起點(diǎn)經(jīng)過(guò)的中間節(jié)點(diǎn),不需要計(jì)算終點(diǎn)到其他節(jié)點(diǎn)的路徑長(zhǎng)度,故該算法的效率大大提高,整個(gè)算法的運(yùn)行時(shí)間為o(n). 所以本文所提出的算法較傳統(tǒng)的Dijkstra算法的運(yùn)算效率要高.

5結(jié)語(yǔ)

基于極小代數(shù)所提出的求解最短路徑代數(shù)算法通過(guò)賦權(quán)有向圖的直接距離矩陣A,計(jì)算k步最短路徑距離矩陣Ak和最短路徑距離矩陣A+,依次求解賦權(quán)有向圖的最短路徑以及最少步數(shù)最短路徑,并且應(yīng)用實(shí)例驗(yàn)證了算法的正確性及有效性.本文所提出的代數(shù)算法與傳統(tǒng)的基于網(wǎng)絡(luò)分析的求解最短路徑方法相比更加規(guī)范、系統(tǒng),邏輯性強(qiáng),并且思路清晰. 從代數(shù)的角度觀察、分析路徑規(guī)劃問(wèn)題,能夠更加容易看清問(wèn)題的本質(zhì),算法比較容易建立、分析和實(shí)現(xiàn).

參考文獻(xiàn):

[ 1 ] 甘應(yīng)愛(ài),田豐,錢頌迪. 運(yùn)籌學(xué)[M]. 北京: 清華大學(xué)出版社, 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ìn)展[J]. 測(cè)繪學(xué)報(bào), 2001,30(3):269-275.

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

[ 5 ] 宮恩超,李魯群. 基于Bellman-Ford算法的動(dòng)態(tài)最優(yōu)路徑算法設(shè)計(jì)[J]. 測(cè)繪通報(bào), 2011(8):26-28,41.

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

[ 6 ] 鮑培明. 距離尋優(yōu)中Dijkstra算法的優(yōu)化[J]. 計(jì)算機(jī)研究與發(fā)展, 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 ] 王銀燕,余鎮(zhèn)危,曹懷虎,等. 基于二度量的單播最短路徑算法[J]. 計(jì)算機(jī)工程, 2007,33(5):89-90.

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

[ 9 ] 王志和,凌云.Dijkstra最短路徑算法的優(yōu)化及其實(shí)現(xiàn)[J]. 微計(jì)算機(jī)信息, 2007,23(33):275-277.

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

[10] 盧香清,李洪安,康寶生,等. 圖最短路徑并行化機(jī)器應(yīng)用研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012,48(14):38-43.

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

[11] 李元臣,劉維群. 基于Dijkstra算法的網(wǎng)絡(luò)最短路徑分析[J]. 微計(jì)算機(jī)應(yīng)用, 2004,25(3):295-298.

【責(zé)任編輯: 李艷】

(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

中圖分類號(hào):TP 301.6

文獻(xiàn)標(biāo)志碼:A

作者簡(jiǎn)介:李彥平(1957-),男,遼寧錦州人,沈陽(yáng)大學(xué)教授,博士.

基金項(xiàng)目:國(guó)家自然科學(xué)基金青年科學(xué)基金資助項(xiàng)目(61203152); 遼寧省博士科研啟動(dòng)基金資助項(xiàng)目(20121040).

文章編號(hào):2095-5456(2015)01-0025-05