基于矩陣運算K短路徑算法

趙禮峰，黃奕雯

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046)

基于矩陣運算K短路徑算法

趙禮峰，黃奕雯

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046)

最短路問題是復(fù)雜網(wǎng)絡(luò)中的經(jīng)典問題，其求解算法層出不窮，各有優(yōu)缺點。經(jīng)典的算法包括Dijkstra算法、Ford算法和Floyd算法等，只能求解兩節(jié)點間的一條最短路徑。在實際生活中，還需要在大型網(wǎng)絡(luò)中限定一些前提條件求解兩點間次短、漸次短的路徑問題。為此，提出了一種對距離矩陣和路徑矩陣的迭代、替換算法，即從一個節(jié)點出發(fā)尋找其后繼節(jié)點，同時通過比較路徑長短得到兩點間最短路徑、次短路徑和漸次短路徑，并不斷重復(fù)、替換。為驗證所提算法的有效性，以一個大型網(wǎng)絡(luò)的應(yīng)用作為實例，應(yīng)用Matlab對所提算法進行了仿真實驗驗證。仿真結(jié)果表明，所提算法能夠在復(fù)雜大規(guī)模隨機網(wǎng)絡(luò)中滿足求解指定頂點間最短、次短和漸次短路徑的需要，具有較好的有效性和適用性。

次短路徑；漸次短路徑；距離矩陣；路徑矩陣

0 引 言

最短路徑問題是復(fù)雜網(wǎng)絡(luò)中一大經(jīng)典問題，它的應(yīng)用領(lǐng)域十分廣泛，如通信網(wǎng)絡(luò)、物流運輸、地理信息系統(tǒng)、軍事運籌學(xué)和旅行規(guī)劃等等[1]。經(jīng)典算法[2]卻只能解決兩節(jié)點間一條最短路，而在這些實際運用中，往往不僅僅考慮一條最短路徑，還要根據(jù)實際情況及具體要求選擇其次短路徑、漸次短路徑。比如說在旅行線路的規(guī)劃問題上，所要選擇的路線不一定是距離最短的路線，還要考慮實際路況、天氣、經(jīng)濟效益等因素，那么就需要篩選出不止一條短路徑。

對于K短路徑問題，國內(nèi)外學(xué)者們已經(jīng)取得了一些研究成果。例如，Eppstein給出了一個允許有向圖上的路徑環(huán)存在的算法[3]；陳文蘭等提出了一種求解次短和漸次短路徑的實用算法[4]；Yen提出了一種無環(huán)的K短路算法[5]，趙見在他的基礎(chǔ)上提出了求解無環(huán)K短路徑的Dijkstra算法[6]；柴登峰[7]、牛新奇[8]等通過刪去最短路中某些邊以及邊對得到新的子圖，再從子圖中求得最短路，然后通過排序的方法得到前K條短路徑。之后，王文寧提出了基于優(yōu)化的Floyed算法前r條最短路徑的實現(xiàn)[9]。

在之前算法的基礎(chǔ)上，又由Floyed的算法特性得出了任意節(jié)點間最短路、次短路以及漸次短路的路長，但是無法得出具體路徑。

為此，在研究上述算法的基礎(chǔ)上，提出了距離矩陣和路徑矩陣的迭代、替換算法，通過矩陣計算最短、次短、漸次短路徑問題。理論分析和仿真實驗結(jié)果均表明：該算法簡便有效、實用性較強，適用于大型復(fù)雜網(wǎng)絡(luò)的求解。

1 相關(guān)知識

定義1[6,10]前K條最短路徑問題：設(shè)有賦權(quán)圖G(V,E)及其上給定的兩個頂點vi和vj,r為vi和vj之間的一條路徑,記其長度為d(r),由vi和vj之間的所有互不相同的路徑組成的集合R(G,vi,vj)稱為G上vi和vj之間的路徑集合,即R(G,vi,vj)={r|r為G上vi,vj之間的路徑}。若按路徑長度值大小將其排列得r1,r2,…,rM,d(r1)≤d(r2)…≤d(rM),則稱r1為G上vi和vj間的第1最短路徑(即狹義最短路徑),d1為其長度;r2為G上vi和vj間第2最短路徑,d2為其長度;rM為G上vi和vj間第M最短路徑,dM為其長度。求取G上vi和vj間的第1～K(K≤M)最短路徑的問題稱為前K條最短路徑問題。

定義2 最短路徑：K=1時的K短路徑，記作PF。

定義3 次短路徑：K=2時的K短路徑，記作PS。

定義4 漸次短路徑：K=3時的K短路徑，記作PT。

定義5 距離矩陣T：在n個節(jié)點的網(wǎng)絡(luò)G(V,E,1)中，距離矩陣T=(tij)n×3。其中，ti0為節(jié)點vi到其他各節(jié)點的最短路徑長；ti1為節(jié)點vi到其他各節(jié)點的次短路徑長；ti2為節(jié)點vi到其他各節(jié)點的漸次短路徑長。

定義6 路徑矩陣F：在n個節(jié)點的網(wǎng)絡(luò)G(V,E,I)中，路徑矩陣F=(fij)n×3,fij為收點的前點標號。

引理1[4]：設(shè)PSij是從頂點vi到頂點vj的次短路徑,對于任意頂點vk∈PSij,若vk∈PFij,則有：

(1)PFij=PFik∪PFkj;

(2)PSij=PFik∪PSkj或PSik∪PFkj。

若vk?PFij,則PSij=PFik∪PFkj。

引理2[4]：設(shè)PTij是從頂點vi到頂點vj的漸次短路徑,對于任意頂點vk∈PTij,若vk∈PFij,則有：

(1)PFij=PFik∪PFkj;

(2)PTij=PTik∪Pkj或PFik∪PTkj或PSik∪PSkj。

若vk∈PSij且vk?PFij,則PSij=PFik∪PSkj。若vk?PFij且vk?PSij,則PTij=PFik∪PFkj。

2 算 法

2.1 算法思想

在文獻[4]提出的算法中，由引理1和引理2得知，要求從頂點vi到頂點vj的最短路徑、次短路徑、漸次短路徑，只需要從頂點vi開始，依次對每個頂點求它的最短路徑、次短路徑和漸次短路徑，并逐次向后擴展，直到達到目標頂點vj，即可求得。文獻[4]首先引入了四組變量：L,T,F,S。每組變量的意義及取值如下：l是對節(jié)點選擇的標記，初始化為(0,0,0)。當l=0時，為臨時標號；當l=1時，為永久標號。t的取值為每次求出的路徑長度，初始化為(∞，∞，∞)，從左到右依次為最短路長、次短路長和漸次短路長。f為收點的前點標號，初始化為(-1，-1，-1)，從左到右依次為最短路徑收點的前點標號，次短路徑收點的前點標號和漸次短路徑收點的前點標號。s是對路徑種類的標記，初始化為(-1，-1)。當s=0時，前段路徑為最短路徑；當s=1時，前段路徑為次短路徑；當s=2時，前段路徑為漸次短路徑。

具體算法概述如下：

Step1:初始化。

Step4:若min選定的是t1的值，則s=0;選定的是t2的值，則s=1;選定的是t3的值，則s=2。

2.2 算法步驟

Step4：令k:=k+1，轉(zhuǎn)到Step2，直到mink=∞時，結(jié)束。

3 算法復(fù)雜度及合理性分析

3.1 空間復(fù)雜度

該算法在網(wǎng)絡(luò)圖中的存儲結(jié)構(gòu)[11]為兩個n×3的矩陣—距離矩陣T和路徑矩陣F。因此該算法的空間復(fù)雜度為O(3n+3n)=O(6n)。

3.2 時間復(fù)雜度

該算法的核心是在每次迭代中尋找最短的一條路徑，次短的一條路徑，漸次短的一條路徑,然后進行排列得到其K短路徑。那么每次在距離矩陣T中尋找路程最短的路都要遍歷整個距離矩陣T，而路徑矩陣F也隨距離矩陣T的變化而變化。其時間復(fù)雜度為O(3n)，而整個算法的運行需要做3n次循環(huán)，所以總的算法復(fù)雜度為O(3n×3n)=O(n2)。

3.3 合理性分析

基于矩陣運算K短路徑算法是基于文獻[4]中的算法在運算的存儲結(jié)構(gòu)上的一種改進[12]，從而簡化運算同時節(jié)省了存儲空間，所以原文中的定理即文中的引理可以說明次短路和漸次短路求解的正確性。同時由于該算法中最短路的求解是基于經(jīng)典最短路算法Dijkstra，所以使用該算法無法解決含有賦權(quán)值的網(wǎng)絡(luò)。

4 應(yīng)用實例

例題：南京旅游局開通了一條旅行專線[13],途中經(jīng)過5個景點(奧體中心、中山陵、夫子廟、中華門、玄武湖)，每班車的發(fā)車時間固定,如果在某一時刻出發(fā)從一個景點到另一個景點,討論不同時刻出發(fā)去某一景點的最短時間。

班車時刻表如表1所示。

表1 班車時刻表

問：(1)某人在11:30要從奧體中心出發(fā)去中山陵游玩，怎樣乘車才能最快到達？

(2)由于南京道路在節(jié)假日及上下班高峰期時常發(fā)生擁堵，尤其是第一問中求出的最短路中由夫子廟到中山陵這段路，而且最短路線中從奧體中心到中山陵只路過夫子廟這一個景點，可參觀地點較少，所以希望再設(shè)計出從奧體中心到中山陵的次短路徑以及漸次短路徑，這樣既可以參觀更多的景點,又可以在發(fā)生大規(guī)模擁堵的情況下可以選擇較為暢通的路線行駛。

解：(1)把換乘旅行班車問題運用到圖論中轉(zhuǎn)化為最短路問題。首先，令奧體中心為A點(該例中作為發(fā)點)，夫子廟為B點，中華門為C點，玄武湖為D點，中山陵為E點(該例中作為收點)，做出旅行班車的路線圖。因為旅行班車?？奎c時間固定，所以不同的出發(fā)時間，會有不同的時間圖，即圖中邊上的權(quán)值不同。圖1為11:30時出發(fā)的路線圖，為賦權(quán)無回路有向圖。

圖1 景點分布圖

任意使用一種最短路問題的算法求得從奧體中心(A)到中山陵(E)最快需要90min，路線為：奧體中心(A)→夫子廟(B)→中山陵(E)。

(2)用文中提出的算法首先得到以上賦權(quán)有向圖的距離權(quán)矩陣D：

接著初始化距離矩陣和路徑矩陣，根據(jù)算法逐次迭代，計算過程如下：

所以，得到結(jié)論如下：

A→B：A→B=45

A→C：A→B→C=65，A→C=90

A→D：A→B→D=80，A→B→C→D=80，A→C→D=105

A→E：A→B→E=90，A→B→D→E=135，A→B→C→D→E=135

可以看到，從奧體中心(A)到中山陵(E)次短路線需要135min，路線為：奧體中心(A)→夫子廟(B)→玄武湖(D)→中山陵(E)；漸次短路線也需要135min，路線為：奧體中心(A)→夫子廟(B)→中華門(C)→玄武湖(D)→中山陵(E)。

從結(jié)論可以看出，如果選擇漸次短路線，那么可以在一天去完所有景點，但如果考慮游覽的時間，選擇次短路線既可避開擁堵道路，也可以增加一個景點游玩。

5 算法仿真(摘自2015年研究生數(shù)學(xué)建模F題第一問)

旅游路線規(guī)劃問題：

旅游活動正在成為全球經(jīng)濟發(fā)展的重要動力之一，它加速了國際資金流轉(zhuǎn)和信息、技術(shù)管理的傳播，創(chuàng)造了高效率的消費行為模式、需求和價值等。隨著國民經(jīng)濟的快速發(fā)展，人們生活水平得到很大提升，越來越多的人開始積極參與有益于身心健康的旅游活動。

現(xiàn)有一批自駕游愛好者希望從北京出發(fā)自駕去新疆游玩，沿途可以邊走邊玩。根據(jù)各省會城市之間公路里程信息，利用上述算法得出前K條短路徑，以便各位自駕游車主選擇適合自己的線路。

由于要求的旅行線路問題，是由31個省作為31個節(jié)點，省會間距離作為權(quán)值構(gòu)成的有向賦權(quán)網(wǎng)絡(luò)，大致網(wǎng)絡(luò)圖如圖2所示。這是一個較為大型的網(wǎng)絡(luò)，數(shù)值計算較為麻煩，在Matlab[14]中對該算法進行仿真從而得出結(jié)果。

仿真結(jié)果均是在CPU為InterCore(TM)i5-4200M,2.50Hz,內(nèi)存8GB,MATLABR2009b環(huán)境下運行實現(xiàn)的。

部分具體行程表(按路徑長度生序排列)如表2所示，起點和終點分別為北京和烏魯木齊。路程按照省會間距離計算。

由表2可以看出,可以針對自駕游車主的不同要求為其制定適合的旅行線路：比如，若該自駕游車主需要最快的線路，那么可以為他推薦線路1(最短路線路)；若該自駕游車主希望在旅行中經(jīng)過石家莊市辦事，可以為他推薦線路2(次短路線路)；若該自駕游車主同時游覽超過5個省，可以為他推薦線路3(漸次短路線路)。

圖2 省間距離圖 表2 具體行程表

線路途經(jīng)省、市總路程/km1(最短路)內(nèi)蒙古呼和浩特市、甘肅省蘭州市35202(次短路)河北省石家莊市、內(nèi)蒙古呼和浩特市、甘肅省蘭州市38203(漸次短路)河北省石家莊市、山西省太原市、內(nèi)蒙古呼和浩特市、甘肅省蘭州市3980

6 結(jié)束語

針對傳統(tǒng)算法只能解決一條最短路的局限性，提出了一種通過距離矩陣的迭代操作和路徑矩陣的替換操作得出前K條短路徑的算法。該算法利用矩陣進行記錄和計算，一定程度上簡化了仿真的復(fù)雜性。在理 論分析的基礎(chǔ)上，進行了相關(guān)實例仿真計算，以驗證該算法的有效性和可行性。理論分析及仿真驗證結(jié)果表明，該算法基于Matlab平臺對于包括生活中旅行線路選擇問題在內(nèi)的大型復(fù)雜網(wǎng)絡(luò)求解具有較好的實用性。

[1] 謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長沙:國防科技大學(xué)出版社,2003.

[2] 劉煥淋,陳 勇.通信網(wǎng)圖論及應(yīng)用[M].北京:人民郵電出版社,2010.

[3]EppsteinD.Findingthekshortestpaths[J].SIAMJournalofComputing,1998,28：652-673.

[4] 陳文蘭,潘蔭榮.一個求解次短和漸次短路徑的實用算法[J].計算機應(yīng)用與軟件,2006,23(1):94-96.

[5]YenJY.Findingthekshortestlooplesspathsinanetwork[J].ManagementScience,1971,17(11):712-716.

[6] 趙 見.求解無環(huán)K短路徑的Dijkstra算法[J].淮陰師范學(xué)院學(xué)報:自然科學(xué)版,2012,11(1):8-12.

[7] 柴登峰,張登榮.前N條最短路徑問題的算法及應(yīng)用[J].浙江大學(xué)學(xué)報:工學(xué)版,2002,36(5):531-534.

[8] 牛新奇,潘蔭榮,胡幼華.K(≤3)條漸次短路徑搜索算法的研究[J].計算機工程與應(yīng)用,2005,41(22):51-53.

[9] 王文寧.基于優(yōu)化的Floyed算法前r條最短路徑的實現(xiàn)[J].常州工學(xué)院學(xué)報,2009,22(5):28-30.

[10]HoffmanW,PavleyR.AmethodofsolutionoftheNthbestpathproblem[J].JournaloftheACM,1959,6(4):506-514.

[11]KatohN,IbarakiT,MineH.Anefficientalgorithmforkshortestsimplepaths[J].Networks,1982(12):411-427.

[12] 高 松,陸 鋒.K則最短路徑算法效率與精度評估[J].中國圖象圖形學(xué)報,2009,14(8):1677-1683.

[13] 張國伍,錢大琳.公共交通線路網(wǎng)多條最短路徑算法[J].系統(tǒng)工程理論與實踐,1992,23(4):22-26.

[14] 劉衛(wèi)國.MATLAB程序設(shè)計與應(yīng)用[M].北京:高等教育出版社,2006.

Research onK-shortest Path Algorithm with Matrix Operations

ZHAO Li-feng,HUANG Yi-wen

(College of Mathematics and Physics,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

Shortest path problem is a classic problem in complex networks,and their solutions after another and all have their advantages and disadvantages.The algorithm of Dijkstra,Ford and Floyd are most classical among these algorithms.However,these algorithms are only for solving a shortest path between nodes.In real life,some limited prerequisites are needed to find the second shortest path and the third shortest path between two nodes in large-scale networks.Therefore,the iterating and displacement algorithm for distance matrix and path matrix is proposed，started from one node to its successor node then compared to find the first shortest path,the second shortest path and the third shortest path repeating and replacing constantly.In order to verify the effectiveness of the proposed algorithm,taking a large network as an example,Matlab is applied to identify it in simulation.It is demonstrated that the proposed algorithm can calculate the first shortest path,the second shortest path and the third shortest path in a complex large-scale random networks,with good validity and applicability.

second shortest path;third shortest path;distance matrix;channel matrix

2016-04-22

2016-08-11

時間：2017-03-07

國家自然科學(xué)基金資助項目(61304169)

趙禮峰(1959-),男,教授,碩士研究生導(dǎo)師,研究方向為圖論及其在通信中的應(yīng)用;黃奕雯(1991-),女,碩士研究生,研究方向為圖論及其在通信中的應(yīng)用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0920.002.html

TP301.6

A

1673-629X(2017)04-0098-06

10.3969/j.issn.1673-629X.2017.04.022