基于矩陣自定義運(yùn)算的Floyd改進(jìn)算法

趙禮峰，黃奕雯

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

基于矩陣自定義運(yùn)算的Floyd改進(jìn)算法

趙禮峰，黃奕雯

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

解決最短路問題的算法層出不窮，其中最經(jīng)典的要數(shù)Dijkstra算法和Floyd算法。但Dijkstra算法只能得出一對(duì)節(jié)點(diǎn)間的最短距離，而Floyd算法計(jì)算過程十分繁瑣。為解決這兩種經(jīng)典算法中的缺陷，提出一種基于矩陣自定義運(yùn)算的Floyd改進(jìn)算法。該算法通過自定義矩陣運(yùn)算得出一個(gè)表示兩兩節(jié)點(diǎn)間距離的路權(quán)修正矩陣，再用路權(quán)修正矩陣與原距離矩陣進(jìn)行比較，選擇兩矩陣中對(duì)應(yīng)較小元素組成當(dāng)前最短路權(quán)矩陣，再通過有限次的迭代，從而得到各頂點(diǎn)間的最短路。通過MATLAB仿真，將該算法推廣到隨機(jī)大規(guī)模復(fù)雜網(wǎng)絡(luò)中，通過運(yùn)行時(shí)間折線圖表明，該算法在節(jié)點(diǎn)達(dá)到一定數(shù)量后運(yùn)行速度明顯優(yōu)于傳統(tǒng)算法，且在稀疏網(wǎng)絡(luò)中運(yùn)行效率非常高，說明了該算法的有效性。最后，通過具體應(yīng)用說明了該算法的實(shí)用性。

最短路問題;Floyd算法;矩陣自定義運(yùn)算;MATLAB;稀疏網(wǎng)絡(luò)

0 引 言

隨著社會(huì)的發(fā)展，最短路問題在日常生活中的應(yīng)用越來越廣泛，小到上班上學(xué)走哪條路最近，大到網(wǎng)絡(luò)路由以及基站的選址，還有交通旅行、城市規(guī)劃、電網(wǎng)架設(shè)，最短路問題出現(xiàn)在生活的方方面面。如果掌握了最短路算法，那么可以給生活帶來許多便利。為了解決簡單的最短路問題，提出了許多簡便的算法，如Dijkstra算法、Floyd算法、Kruskal算法、拓?fù)渑判蚍?、啟發(fā)式搜索算法、A*算法、動(dòng)態(tài)規(guī)劃算法以及神經(jīng)網(wǎng)絡(luò)遺傳算法等等[1-6]。然而Dijkstra算法和Floyd算法無法解決任意頂點(diǎn)間最短路長的問題，而且Floyd算法十分繁瑣。

針對(duì)上述問題，文中提出了一種基于矩陣自定義運(yùn)算的Floyd改進(jìn)算法。該算法在計(jì)算權(quán)矩陣時(shí)直接在權(quán)值旁對(duì)路徑進(jìn)行標(biāo)注，省去了路徑矩陣的求解。同時(shí)，在運(yùn)算過程中對(duì)矩陣元素出現(xiàn)∞時(shí)不進(jìn)行運(yùn)算，大大簡化了運(yùn)算量。特別是在稀疏矩陣中，由于稀疏矩陣中有大量的∞元素，那么只需計(jì)算其中幾個(gè)非∞元素，算法優(yōu)勢(shì)顯而易見。但是當(dāng)階數(shù)n非常大時(shí)，計(jì)算依然十分復(fù)雜，所以需要借助計(jì)算機(jī)用計(jì)算機(jī)語言來實(shí)現(xiàn)大型網(wǎng)絡(luò)的計(jì)算。文中借助MATLAB實(shí)現(xiàn)該算法。

1 相關(guān)知識(shí)

定義1[7]賦權(quán)圖：設(shè)G=(V,E)為一幅圖，給G的每一條邊e賦予一個(gè)權(quán)值w(e),w(e)可以指網(wǎng)絡(luò)流量、運(yùn)輸費(fèi)用、物理距離、消耗時(shí)間等。若圖G的所有邊都賦予權(quán)值，稱G為賦權(quán)圖或網(wǎng)絡(luò)。

定義2[7]最短路徑：在帶權(quán)圖G=(V,E)中，若頂點(diǎn)vi，vj是圖G的兩個(gè)頂點(diǎn)，從頂點(diǎn)vi到vj的路徑長度定義為路徑上各條邊的權(quán)值之和。從頂點(diǎn)vi到vj可能有多條路徑，其中路徑長度最小的一條稱為頂點(diǎn)vi到vj的最短路徑。

定義4[3]稀疏網(wǎng)絡(luò)：用稀疏矩陣存儲(chǔ)的網(wǎng)絡(luò)。

定義5、定義6是文中給出的：

定義5 稀疏矩陣：包含大量0元素的矩陣，在最短路問題中，可以認(rèn)為含有大量∞元素的矩陣。

定義6 矩陣自定義運(yùn)算⊕：現(xiàn)定義一種運(yùn)算⊕，使得：

那么有：

這種新定義的運(yùn)算相當(dāng)于連接兩條經(jīng)過統(tǒng)一定點(diǎn)的路徑。每做一次⊕運(yùn)算相當(dāng)于原路徑經(jīng)過一次中間節(jié)點(diǎn)。

(1)

2 基于矩陣自定義運(yùn)算的Floyd改進(jìn)算法

2.1 算法思想

與此同時(shí)，以標(biāo)注法直接在代表距離的權(quán)值旁的括號(hào)中標(biāo)注路徑。當(dāng)插入某個(gè)節(jié)點(diǎn)vk后，若計(jì)算出的最短路徑長度小于原來不經(jīng)過vk時(shí)的長度，那么就將該節(jié)點(diǎn)的下標(biāo)k直接標(biāo)注在權(quán)矩陣中對(duì)應(yīng)的元素的右邊括號(hào)中表明vk為最短路中路過節(jié)點(diǎn)，若路過節(jié)點(diǎn)不止一個(gè)則依次標(biāo)明。

最后，當(dāng)加法運(yùn)算中一個(gè)加法項(xiàng)dij出現(xiàn)∞時(shí)，不用計(jì)算，直接得∞；當(dāng)加法項(xiàng)dij出現(xiàn)0時(shí)，同樣無需計(jì)算，直接寫上另一個(gè)加法項(xiàng)，從而簡化計(jì)算。

2.2 算法步驟

Step2:如果k=n，結(jié)束；否則，令k:=k+1,轉(zhuǎn)Step1。

2.3 算法復(fù)雜度分析

3 算 例

以圖1為例，得出各個(gè)頂點(diǎn)間的最短路。

圖1 稀疏網(wǎng)絡(luò)

所以，經(jīng)過V2和U0的比較，有

所以，經(jīng)過V4和U2的比較，有

由于最后一行不用計(jì)算，所以U5=U4即為最終得出的結(jié)果。

4 算法的仿真與可行性分析

利用MATLAB[10]對(duì)文中提出的算法進(jìn)行仿真。首先運(yùn)行普通網(wǎng)絡(luò)，接著運(yùn)行稀疏網(wǎng)絡(luò)，同時(shí)與傳統(tǒng)算法的運(yùn)行作對(duì)比，通過運(yùn)行時(shí)間的長短說明該算法的優(yōu)越性。由仿真結(jié)果可知，該算法可以推廣到大規(guī)模隨機(jī)復(fù)雜網(wǎng)絡(luò)中，進(jìn)一步說明了該算法的實(shí)用性。

由于是隨機(jī)生成的網(wǎng)絡(luò)，每次的運(yùn)行結(jié)果有所差別，所以對(duì)它的運(yùn)行時(shí)間取一個(gè)平均值。表1為對(duì)10階，20階，直到100階矩陣運(yùn)行20次取得的平均結(jié)果，將它的運(yùn)行時(shí)間與傳統(tǒng)Floyd算法進(jìn)行比較。圖2為該改進(jìn)算法與傳統(tǒng)算法運(yùn)行時(shí)間相比的折線圖。

表1 算法運(yùn)行時(shí)間

圖2 算法運(yùn)行時(shí)間對(duì)比折線圖

5 實(shí)際應(yīng)用舉例

最短路問題的應(yīng)用非常廣泛,舉一個(gè)實(shí)際生活中存在的旅游班車選乘問題[11-14]的例子來說明最短路問題在生活中的應(yīng)用。

例：南京旅游局開通了一條旅行專線,途中經(jīng)過5個(gè)景點(diǎn)(奧體中心(A)、夫子廟(B)、中華門(C)、玄武湖(D)、中山陵(E))，每班車的發(fā)車時(shí)間固定(見表2)。如果在某一時(shí)刻出發(fā)從一個(gè)景點(diǎn)到另一個(gè)景點(diǎn),討論不同時(shí)刻出發(fā)去某一景點(diǎn)的最短時(shí)間。(將路途中經(jīng)過的時(shí)間看作是路的權(quán)值,那么，求最短時(shí)間的問題就可以看作是求最短路問題,即可以用文中求最短路的方法來解決。)

表2 班車時(shí)刻表

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

解：把換乘旅行班車問題運(yùn)用到圖論中轉(zhuǎn)化為最短路問題。首先，令?yuàn)W體中心為A點(diǎn)(在本例中作為發(fā)點(diǎn))，中山陵作為E點(diǎn)(在本例中作為收點(diǎn))，做出旅行班車的路線圖，因?yàn)槁眯邪嘬囃？奎c(diǎn)時(shí)間固定，所以不同的出發(fā)時(shí)間，會(huì)有不同的時(shí)間圖，即圖中邊上的權(quán)值不同。圖3為11:30時(shí)出發(fā)的路線圖，為賦權(quán)無回路有向圖。

圖3 景點(diǎn)分布圖

初始矩陣為：

用以上算法求解最終得到：

由于最后一行不用計(jì)算，所以U5=U4即為最終得出的結(jié)果。

即，從奧體中心(A)到中山陵(E)最快需要90min，行駛路線為：奧體中心(A)→夫子廟(B)→中山陵(E)。

6 結(jié)束語

通過應(yīng)用實(shí)例可以看出該算法在實(shí)際運(yùn)用中的作用；經(jīng)過程序測試，算法能夠得到任意節(jié)點(diǎn)間最短路。由仿真結(jié)果可以看出，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)較小時(shí)，該算法在一般網(wǎng)絡(luò)中與傳統(tǒng)算法相比，運(yùn)行時(shí)間并沒有得到明顯提高；但是，當(dāng)節(jié)點(diǎn)增多到50個(gè)以上時(shí)，該算法明顯快于傳統(tǒng)算法。同時(shí)，在稀疏網(wǎng)絡(luò)中，無論從時(shí)間復(fù)雜度，還是空間復(fù)雜度來說，文中算法優(yōu)越性明顯。

[1] 張德全,吳果林,劉登峰.最短路問題的Floyd加速算法與優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(17):41-43.

[2] 張德全,吳果林.最短路問題的Floyd算法優(yōu)化[J].許昌學(xué)院學(xué)報(bào),2009,28(2):10-13.

[3] 吳果林,金 珍,鄧小方.稀疏網(wǎng)絡(luò)的Floyd動(dòng)態(tài)優(yōu)化算法[J].江西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2013,37(1):28-32.

[4] 鄧方安,雍龍泉,周 濤,等.基于“矩陣乘法”的網(wǎng)絡(luò)最短路徑算法[J].電子學(xué)報(bào),2009,37(7):1594-1598.

[5] 趙禮峰,梁 娟.最短路問題的Floyd改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(8):31-34.

[6] 鄒桂芳,張培愛.網(wǎng)絡(luò)優(yōu)化中最短路問題的改進(jìn)Floyd算法[J].科學(xué)技術(shù)與工程,2011,11(28):6875-6878.

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

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

[9] Hougardy S. The Floyd-warshall algorithm on graphs with negative cycles[J].Information Processing Letters，2010,110:279-281.

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

[11] 李 科,袁 明.小件快運(yùn)中的最短運(yùn)輸時(shí)間問題[J].山東交通科技,2011(5):23-25.

[12] Feillet D,Dejax P,Gendreau M.Traveling salesman problems with profits[J].Transportation Science,2005,39(2):188-205.

[13] Braess D,Nagurney A,Wakolbinger T.On a paradox of traffic planning[J].Transportation Science,2005,39(4):446-450.

[14] Zhan F B.Three fastest shortest path algorithms on real road networks[J].Journal of Geographic Information and Decision Analysis,1997,1(1):69-82.

Improved Floyd Algorithm Based on Customized Matrix Operations

ZHAO Li-feng,HUANG Yi-wen

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

The algorithm to solve the shortest path problem is endless,and the algorithm of Dijkstra and Floyd is the most typical.However,the Dijkstra algorithm can only get the shortest distance between a pair of nodes,and Floyd algorithm is very cumbersome.For solving their defects in two classical algorithms,an improved Floyd algorithm is proposed based on matrix custom operation.It obtains a modified matrix between two nodes by using a customized matrix calculation,and then compares the modified matrix with the original distance matrix,selecting the smaller matrix elements for composition of the shortest path weight matrix.Through finite iteration,the shortest path is obtained between each vertex.By the MATLAB simulation,the algorithm is extended to stochastic large-scale complex networks.The running time line chart shows that this algorithm runs faster than traditional algorithm after a certain number of nodes,and in sparse network,the efficiency is particularly high,which shows the its effectiveness.Finally,by using the specific application,the feasibility of the algorithm is verified.

shortest path problem;Floyd algorithm;matrix custom operations;MATLAB;sparse network

2015-11-23

2016-03-03

時(shí)間：2016-08-01

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

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

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0904.024.html

TP301.6

A

1673-629X(2016)10-0041-04

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