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

趙禮峰，黃奕雯

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

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

趙禮峰，黃奕雯

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

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

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

0 引 言

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

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

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

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

1 相關知識

定義1[6,10]前K條最短路徑問題：設有賦權圖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個節點的網絡G(V,E,1)中，距離矩陣T=(tij)n×3。其中，ti0為節點vi到其他各節點的最短路徑長；ti1為節點vi到其他各節點的次短路徑長；ti2為節點vi到其他各節點的漸次短路徑長。

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

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

(1)PFij=PFik∪PFkj;

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

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

引理2[4]：設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是對節點選擇的標記，初始化為(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，轉到Step2，直到mink=∞時，結束。

3 算法復雜度及合理性分析

3.1 空間復雜度

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

3.2 時間復雜度

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

3.3 合理性分析

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

4 應用實例

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

班車時刻表如表1所示。

表1 班車時刻表

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

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

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

圖1 景點分布圖

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

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

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

所以，得到結論如下：

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)。

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

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

旅游路線規劃問題：

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

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

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

仿真結果均是在CPU為InterCore(TM)i5-4200M,2.50Hz,內存8GB,MATLABR2009b環境下運行實現的。

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

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

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

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

6 結束語

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

[1] 謝 政.網絡算法與復雜性理論[M].長沙:國防科技大學出版社,2003.

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

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

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

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

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

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

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

[9] 王文寧.基于優化的Floyed算法前r條最短路徑的實現[J].常州工學院學報,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].中國圖象圖形學報,2009,14(8):1677-1683.

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

[14] 劉衛國.MATLAB程序設計與應用[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

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

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

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