趙禮峰，黃奕雯

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

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

趙禮峰，黃奕雯

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

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

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

0 引 言

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

針對(duì)上述問(wèn)題，文中提出了一種基于矩陣自定義運(yùn)算的Floyd改進(jìn)算法。該算法在計(jì)算權(quán)矩陣時(shí)直接在權(quán)值旁對(duì)路徑進(jìn)行標(biāo)注，省去了路徑矩陣的求解。同時(shí)，在運(yùn)算過(guò)程中對(duì)矩陣元素出現(xiàn)∞時(shí)不進(jìn)行運(yùn)算，大大簡(jiǎn)化了運(yùn)算量。特別是在稀疏矩陣中，由于稀疏矩陣中有大量的∞元素，那么只需計(jì)算其中幾個(gè)非∞元素，算法優(yōu)勢(shì)顯而易見(jiàn)。但是當(dāng)階數(shù)n非常大時(shí)，計(jì)算依然十分復(fù)雜，所以需要借助計(jì)算機(jī)用計(jì)算機(jī)語(yǔ)言來(lái)實(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的路徑長(zhǎng)度定義為路徑上各條邊的權(quán)值之和。從頂點(diǎn)vi到vj可能有多條路徑，其中路徑長(zhǎng)度最小的一條稱為頂點(diǎn)vi到vj的最短路徑。

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

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

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

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

那么有：

這種新定義的運(yùn)算相當(dāng)于連接兩條經(jīng)過(guò)統(tǒng)一定點(diǎn)的路徑。每做一次⊕運(yùn)算相當(dāng)于原路徑經(jīng)過(guò)一次中間節(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ì)算出的最短路徑長(zhǎng)度小于原來(lái)不經(jīng)過(guò)vk時(shí)的長(zhǎng)度，那么就將該節(jié)點(diǎn)的下標(biāo)k直接標(biāo)注在權(quán)矩陣中對(duì)應(yīng)的元素的右邊括號(hào)中表明vk為最短路中路過(guò)節(jié)點(diǎn)，若路過(guò)節(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í)，同樣無(wú)需計(jì)算，直接寫(xiě)上另一個(gè)加法項(xiàng)，從而簡(jiǎn)化計(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)過(guò)V2和U0的比較，有

所以，經(jīng)過(guò)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ì)比，通過(guò)運(yùn)行時(shí)間的長(zhǎng)短說(shuō)明該算法的優(yōu)越性。由仿真結(jié)果可知，該算法可以推廣到大規(guī)模隨機(jī)復(fù)雜網(wǎng)絡(luò)中，進(jìn)一步說(shuō)明了該算法的實(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)用舉例

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

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

表2 班車(chē)時(shí)刻表

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

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

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

初始矩陣為：

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

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

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

6 結(jié)束語(yǔ)

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

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

[2] 張德全,吳果林.最短路問(wèn)題的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] 趙禮峰,梁 娟.最短路問(wèn)題的Floyd改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(8):31-34.

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

[7] 謝 政.網(wǎng)絡(luò)算法與復(fù)雜性理論[M].長(zhǎng)沙:國(guó)防科技大學(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)國(guó).MATLAB程序設(shè)計(jì)與應(yīng)用[M].北京:高等教育出版社,2006.

[11] 李 科,袁 明.小件快運(yùn)中的最短運(yùn)輸時(shí)間問(wèn)題[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

國(guó)家自然科學(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