趙美勇　宋思睿

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

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

1 Floyd算法

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

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

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

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

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

2 Dij kstra算法

Dijkstra算法是求單源最短路徑的一種算法，即最短路的起始點(diǎn)唯一。Dijkstra算法是一個(gè)基于貪心的一種算法，其整個(gè)算法的過(guò)程：

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

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

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

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

3 SPFA算法

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

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

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

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

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

4三種算法的比較

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

5總結(jié)

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

參考文獻(xiàn)

[1]Thomas H.Cormen， Charles E.Leiserson， Ronald L.Rivest，Clifford Stein.算法導(dǎo)論[M].殷建平，徐云，王剛，劉曉光，蘇明，鄒恒明，王宏志，譯.北京：機(jī)械工業(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.徐寶文，李志，譯.北京：機(jī)械工業(yè)出版社，2004.

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

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