【摘 要】本文首先從傳統(tǒng)的Floyd算法的機理入手，詳細描述了帶權(quán)有向圖中任意兩點之間的最短路徑求解過程，通過手工模擬構(gòu)造排序矩陣和C語言編程實現(xiàn)，找出影響算法效率的關鍵步驟。

【關鍵詞】Floyd最短路徑算法 手工模擬 語句頻度 優(yōu)化算法

最短路徑的求解算法通常都依賴于一種性質(zhì)，即任意兩點之間的最短路徑，總是也包含了路徑上其他頂點間的最短路徑。帶權(quán)有向圖G的最短路徑問題，一般可分為兩類：一是單源最短路徑，它是指求一個網(wǎng)絡圖中任意一個頂點到其他各頂點之間的最短路徑，目前比較流行的算法是Dijkstra算法[1]。二是求帶權(quán)網(wǎng)絡圖中任意一對頂點間的最短路徑，常常選用Floyd-Warshall算法[2]。除了以上兩種算法之外，目前國內(nèi)外對最短路徑的算法的研究還有A*算法[3]和Bellman-Ford算法[3]等。Dijkstra算法和Floyd算法各有優(yōu)缺點[4]，盡管Dijkstra算法屬于單源最短路徑算法，但也可以用它來解決每對頂點之間的最短路徑問題，每一次執(zhí)行其算法過程時，輪流將一個頂點作為源點即可求出任意兩點之間的最短路徑，算法的時間復雜度為O（n3）。但該算法的缺點是網(wǎng)絡中的邊不能帶有負權(quán)值，否則Dijkstra算法將不再適用。Floyd算法給出了一個解決帶權(quán)圖中任意兩點之間最短路徑問題的一個新方法。Floyd算法的C語言描述如下：

void Floyd（MGraph G，DistanceMatrix D）

for（i=0；i

for（j=0；j

A[i][j]=A.arcs[i][j]； //語句3

for（u=0；u

for（i=0；i

for（j=0；j

if（A[i][u]+A[u][j]

A[i][j]=A[i][u]+A[u][j]； //語句8

在該算法中，MGraph是圖的鄰接矩陣存儲結(jié)構(gòu)體類型，DistanceMatrix是距離矩陣二維數(shù)組類型。該算法的語句執(zhí)行頻度為n3+n2，時間復雜度為O（n3）。很明顯，該算法的缺陷是時間開銷是關于頂點的多項式函數(shù)，跟圖中是否存在邊沒有關系。下面舉例說明該算法的執(zhí)行過程。例：設圖G=（V，E），V={v0，v1，v2}，E={，，，，}。傳統(tǒng)Floyd算法的執(zhí)行過程如表1所示。為了更加詳細的說明矩陣中的元素值是如何計算出來的，現(xiàn)在用手工模擬的方法來實現(xiàn)矩陣A（0）。同理，矩陣A（1）和矩陣A（2）求解方法也是完全相同的。在傳統(tǒng)的Floyd算法中，在計算vi和vj之間的最短路徑時每次都會有n次加法運算，并且大多數(shù)時候插入的中間節(jié)點vk并不能使原來的路徑長度變小，這導致產(chǎn)生了很多沒必要的運算過程，降低了計算的效率。鑒于以上缺陷，本文在降低計算次數(shù)的基礎上對傳統(tǒng)的Floyd算法進行優(yōu)化，從而降低算法的計算量，提高運行效率。 Floyd優(yōu)化新算法的設計。新的Floyd算法的設計目的主要是為了降低傳統(tǒng)算法中的冗余語句處理過程，觀察上文中的傳統(tǒng)Floyd算法的C語言程序，發(fā)現(xiàn)影響整個程序的運行效率的關鍵語句是“語句7”。在該語句中，不論A[i][u]或A[u][j]在進行加法運算之前是否已經(jīng)小于A[i][j]，該加法運算總是要執(zhí)行的。顯然在該if語句中，總共要經(jīng)過2次計算，一次加法計算和一次比較計算。雖然表面上看起來運算次數(shù)并不多，但是由于外面套有三層執(zhí)行次數(shù)各為頂點數(shù)n的for循環(huán)計算，這將會導致該條if語句會被無條件的執(zhí)行n3次，則需要計算的總次數(shù)為2n3次。顯然這是十分降低時間效率的行為，原因是A[i][u]和A[u][j]在進行加法計算之前其中的某一個值已經(jīng)大于或等于A[i][j]的值了，此時僅僅只需要做一次比較運算即可，不需要再額外進行一次加法計算。算法優(yōu)化的基本思想是：對于迭代矩陣A（k），在計算兩點vi和vj之間的最短路徑時，對待插入的節(jié)點vu先進行路長比較，如果或，則說明插入節(jié)點vu之后，點vi途經(jīng)vu到達vj的路程并不比原來從vi到vj的短，從而就不再需要計算vi，vu，vj這三點的路徑之和，從而極大地降低了算法的實際計算量，提高了時間效率。那么，對于經(jīng)過優(yōu)化的Floyd算法而言新的描述為：定義一個n階方陣序列A（-1），A（0），A（1），...，A（n-1），其中k=0，1，2，...，n-1：

A（-1）[i][j]=arcs[i][j]

當A（k-1）[i][u]≥A（k-1）[i][j]或者A（k-1）[u][j]≥A（k-1）[i][j]時，有A（k）[i][j]=A（k-1）[i][j]

A（k）[i][j]=A（k-1）[i][u]+A（k-1）[u][j]

算法步驟中的（2）和（3）這兩者只執(zhí)行一個，當（2）滿足時就會跳過（3）然后繼續(xù)執(zhí)行；當（2）不滿足時就會執(zhí)行（3）然后繼續(xù)執(zhí)行。為了更加直觀的描述新算法的執(zhí)行過程，用實際的編程語言來實現(xiàn)算法的操作。

結(jié)論：綜上可知，優(yōu)化之后的Floyd算法在關鍵語句的執(zhí)行頻度方面為n3+m，遠遠小于傳統(tǒng)的Floyd算法的執(zhí)行頻度2n3。

參考文獻：

[1]孫強，Dijkstra的一種改進算法[J].計算機工程與應用，2003，39（3）：99-101.

[2]Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein.算法導論[M].北京：機械工業(yè)出版社.2006：386-390

作者簡介：

劉瑩，女，1992.6月，回族，本科學歷，專業(yè)方向：信息與計算科學。