三種最短路算法的比較

趙美勇　宋思睿

摘要：在圖這個數(shù)據(jù)結(jié)構(gòu)中，最常見的一種問題就是求這個圖中的給定的起點和終點來找到一條最短的路徑，這不光是計算機的一個問題，同時也是現(xiàn)實生活中可能需要考慮的事情?，F(xiàn)在的各大地圖應(yīng)用，核心算法都是利用的最短路算法，最短路算法有很多種，但是有三個最有名的最短路算法：Floyd、Dijkstra、SPFA，對于這三種算法的使用場景，則是根據(jù)算法的復雜度來決定。因此，將這三種算法在復雜度、優(yōu)化方面進行了比較。

關(guān)鍵字：Floyd Dijkstra SPFA時間復雜度 圖

1 Floyd算法

Floyd最短路算法是基于動態(tài)規(guī)劃思想的一種算法。它的動態(tài)轉(zhuǎn)移方程f[i，j]=min（f[i，j]，f[i，k]+f[k，j]），其算法的具體過程：

（1）定義一個二維數(shù)組f，f[i，j]表示從i到j(luò)的最短距離，在初始化時，將數(shù)組用最大值填充。

（2）根據(jù)圖中的點數(shù)n，然后進行三層枚舉，枚舉的順序為k、l、j，其中k作為枚舉到的中間節(jié)點，i、j分別代表起點和終點，因此它的轉(zhuǎn)移方程f[i，j]=min（f[i，j]，f[i，k]+f[k，j]）表示為，從i到j(luò)的距離是否可以被經(jīng)過中間節(jié)點k組成的i到k再到j(luò)的路徑更新，因為找的是最短路徑，所以選用的mm函數(shù)，如果f[，k]+f[k，j]小于f[i，j]，則更新f[i，j]，反之則不更新。

（3）整個f數(shù)組儲存的都是對應(yīng)點的最短距離，按照要求輸出結(jié)果。

根據(jù)整個算法的描述，可以看出算法的核心是處理轉(zhuǎn)移方程的三重循環(huán)，因此Floyd算法是立方級別的，所以Floyd算法在處理圖比較大的情況時并不適用，它適用一些圖比較小的情況。同時Floyd算法可以拓展，多一層內(nèi)循環(huán)可以衍生出一個新算法就是尋找圖中的最小環(huán)。

2 Dij kstra算法

Dijkstra算法是求單源最短路徑的一種算法，即最短路的起始點唯一。Dijkstra算法是一個基于貪心的一種算法，其整個算法的過程：

（1）確定起點定義一個數(shù)組dist[i]，表示從起點到i點的最短距離，再定義一個數(shù)組flag[i]用來表示i這個點是否被遍歷過。

（2）輸入圖矩陣，初始化dist數(shù)組，如果點i與起始點有邊相連，那么dist[i]的值為他們的邊權(quán)，如果沒有邊相連，則值為無窮大;對于flag數(shù)組的初始化，將起始點標注為1，表示為訪問過，將其他的沒有訪問過的置為O。

（3）遍歷n-l次，表示的是更新n-l次，因為在初始化時已經(jīng)將起始點處理好了。每一次循環(huán)，找到當前距離起始點最近且沒有被訪問過的點，將這個點標記為訪問過，然后用這個點去更新當前的最短路，具體的松弛操作語句為：dist[i]=min（dist[dist[i]+map[i，j]），和Floyd算法的轉(zhuǎn)移方程基本一致。貪心的思想體現(xiàn)在，每次都找當前沒有訪問過且距離最小的點來進行下一次迭代。

根據(jù)整個算法描述，可以看出整個算法的核心循環(huán)是遍歷每一個沒有被訪問過的點，再找到當前結(jié)點的最小點，利用這個最小點來更新其他的點。因此算法的復雜度是平方級別的，但是我們可以注意其中一個步驟，我們再找當前點的最小點的時候可以利用堆來維護一個序列，堆頂就是最小值，雖然優(yōu)化之后的算法復雜度仍是平方級別，但是在某些情況下可能會被卡常數(shù)，因此可以利用這個堆優(yōu)化。

3 SPFA算法

SPFA算法的全稱為Shortest Path Faster Algorithm，即最短路更快算法。SPFA是Bellman-Ford算法的一種隊列優(yōu)化，是一種基于BFS的最短路算法，該算法解決了Dijkstra算法無法解決的變權(quán)為負值的情況，防止負環(huán)的情況導致算法永遠迭代進入死循環(huán)，SPFA的關(guān)鍵一點是圖的存儲，一種是鄰接表，另外一種邊集數(shù)組，又被叫做前向星優(yōu)化，整個算法的過程，這里選取邊集數(shù)組：

（1）確定起點，定義七個數(shù)組分別為：head[i]表示起點為i的邊的序號，dist[i]表示從起點到點l的最短距離，v[i]表示第i條邊指向的點，w[i]表示第i條邊的權(quán)重，next[i]表示第i條邊所連接的另一條邊的邊序號，q數(shù)組表示隊列，flag[i]表示點l是否被訪問過。

（2）首先將dist和flag數(shù)組進行初始化，將dist數(shù)組初始為無窮大，再將flag初始為false。讀入起點和終點，將起點入隊，然后將起點的距離置為O，。

（3取出隊首數(shù)據(jù)并將其flag置為O遍歷所有以該點為起點的邊，獲得改邊所指向的點，然后進行松弛，如果當前這個點沒有被訪問過，則將其入隊，并且將其訪問標志置為l，等迭代完成，當前的dist數(shù)組中所存放的均為最短距離。

根據(jù)整個算法描述可以看出算法的核心就是對于隊列的操作，即為每個點進入隊的次數(shù)，因此它的時間復雜度為O（VE），其中V為每個點的入隊次數(shù)，E表示邊的數(shù)量。但這是平均時間復雜度，最壞的情況，即一個點連接所有的點，此時復雜度最高，和Dijkstra的復雜度一樣高。SPFA在處理負邊權(quán)時，已經(jīng)入隊的點無法再次人隊，只能等待該點在隊列中取出才能再次入隊，這樣就防止了一個負變權(quán)可以無限的震蕩。由于SPFA利用了隊列，則根據(jù)隊列的性質(zhì)，SFPA出現(xiàn)了多種優(yōu)化：SLF優(yōu)化和LLL優(yōu)化等。

4三種算法的比較

這三種算法適用于不同的環(huán)境，對于第一種Floyd算法，它求的是多源最短路，可以得到任何兩個點的最短路徑，但是相應(yīng)的復雜度最高，這種算法比較適用于點不是很多，但是邊有很多的圖。對于第二種Dijkstra，它是最穩(wěn)定的一種最短路算法，基本所有有關(guān)最短路方面的算法都是它的變體，它的復雜度比第一種少了一個數(shù)量級，但是它的算法的優(yōu)化很少，最常見的即為堆優(yōu)化，維護每次迭代取出的最小點。第三種是SPFA，它是爭議最大的算法，這個算法最初由西南交通大學的段凡丁證明并提出的，后來證明段凡丁是錯誤的，SPFA就是Bellman-Ford的隊列優(yōu)化的形式，但對稠密圖，SPFA的表現(xiàn)要比Dijkstra出色。

5總結(jié)

通過對于這三種算法的時間復雜度的分析，以及相應(yīng)的優(yōu)化，還有所適用的環(huán)境討論，可以得出在圖的最短路中，最重要的就是迭代求解的過程，如何優(yōu)化這個過程才是減少時間復雜度的關(guān)鍵，而只是更新進隊入隊、維護最小點數(shù)組，這些只能是解決一些卡常數(shù)的問題。因此，仍然需要更多的知識來優(yōu)化核心的迭代。

參考文獻

[1]Thomas H.Cormen， Charles E.Leiserson， Ronald L.Rivest，Clifford Stein.算法導論[M].殷建平，徐云，王剛，劉曉光，蘇明，鄒恒明，王宏志，譯.北京：機械工業(yè)出版社，2012.

[2]Robert SedgeWick，Kevin Wayne.Algorithms.算法（第4版）[M].4thed.謝路云，譯.北京：人民郵電出版社，2012.

[3]Brian W. Kernighan， Dennis M. Ritchie.The C ProgrammingLanguage[M].2nd ed.徐寶文，李志，譯.北京：機械工業(yè)出版社，2004.

[4]劉汝佳，陳鋒.算法競賽入門經(jīng)典：訓練指南[M]，北京：清華大學出版社，2012.

[5]劉汝佳.算法競賽入門經(jīng)典.第2版[M].北京：清華大學出版社，2014.