幾種經(jīng)典的最短路徑算法比較分析

趙衛(wèi)績，鞏占宇，王 雯，樊守芳

（綏化學(xué)院 信息工程學(xué)院，黑龍江 綏化 152061）

0 前言

最短路徑是圖論與復(fù)雜網(wǎng)絡(luò)分析中的一個經(jīng)典問題[1]，在工程規(guī)劃、地理信息系統(tǒng)、通信和軍事運籌學(xué)等領(lǐng)域有著十分廣泛的應(yīng)用[2].最短路徑問題的目的是尋找圖中兩結(jié)點之間的最短路徑，也就是沿此路徑上各邊的權(quán)值總和（路徑長度）達(dá)到最小[3].近年來，最短路徑問題在交通網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、廠區(qū)布局、旅游路線推薦等實際生活中具有廣泛的應(yīng)用，引起了交通、物流、運籌學(xué)、管理學(xué)、計算機科學(xué)等多領(lǐng)域廣大學(xué)者的關(guān)注，涌現(xiàn)出多種經(jīng)典的最短路徑算法以及相應(yīng)改進算法.這些算法在空間復(fù)雜度、時間復(fù)雜度、易實現(xiàn)性及應(yīng)用范圍等方面各具特色[4-6].文獻[7]給出了一種改進的Dijkstra標(biāo)號算法，有效解決了連通無向帶權(quán)圖和有向帶權(quán)圖的最短路徑問題,文獻[8]對Dijkstra算法進行了改進，有效解決多鄰接點問題與多條最短路徑問題，文獻[9]提出的基于Floyd算法的改進算法可以有效解決多重等價最短路問題，文獻[10]通過對固定序Bellman-Ford算法進行修正，獲得了一種求解邊數(shù)不大于k的最短路問題的新算法，文獻[11]給出了改進的SPFA算法，降低了算法的時間復(fù)雜度，使得對于任意的有向圖，該算法都能夠在O(|V||E|)內(nèi)執(zhí)行完畢.這些最短路徑算法各有其優(yōu)勢，適應(yīng)于不同網(wǎng)絡(luò)結(jié)構(gòu).本文全面地分析了最短路徑問題，對Dijkstra算法、Floyd算法、Bellman-Ford算法、SPFA算法幾種經(jīng)典的最短路徑算法給出全面的闡述，并采用Java語言設(shè)計了一個實驗系統(tǒng)，對這幾種經(jīng)典算法進行驗證實驗，并比較這幾種經(jīng)典的算法在不同網(wǎng)絡(luò)中的運行時間和運行結(jié)果，此外，還對每種算法的適用性進行了分析.

1 相關(guān)定義

1.1 圖

在一個由n個節(jié)點和m條邊組成的圖G(V，E)中，V代表G中所有頂點集合，E代表G中所有邊集合，對稠密圖的定義是有較多條邊或弧的圖(如e＜nlogn)，反之稱為稀疏圖[12].假設(shè)頂點之間的距離為w，則圖中任意兩點之間的距離可以用一個權(quán)值矩陣e來表示.設(shè)置源點為vs，并將源點到自身的距離設(shè)置為0，若兩個頂點之間可達(dá)，則eij可以表示圖中頂點i到頂點j之間的距離，同時把圖中不能直接到達(dá)的頂點之間的距離設(shè)置為無窮大.

1.2 最短路徑

最短路徑問題是求由源點vs到達(dá)圖中任一頂點的最短路徑，即尋找一條路徑，使得這條路徑上的邊的權(quán)值總和∑Wij為最小值.最短路徑問題分為靜態(tài)和動態(tài)等多種形式：靜態(tài)路徑是指在外界環(huán)境不變的基礎(chǔ)上，計算最短路徑；而動態(tài)路徑是指外界環(huán)境不斷發(fā)生變化，在不能預(yù)測的情況下計算最短路徑[7].

1.3 松弛

松弛操作即如果圖中兩點之間存在其他路徑，并且該路徑的距離小于這兩點之間的當(dāng)前距離，那么這兩點之間的最短路徑長度更新為這個更小的距離.若圖中存在頂點無法再進行松弛操作，則稱該頂點已收斂.在圖1中，a點到b點的距離原本為5，但由于從a點出發(fā)經(jīng)由c點也能到達(dá)b點，并且eac+ecb=1+2=3＜5，即新路徑的距離小于原始路徑距離，因此將A點到B點之間的距離更新為3，此時圖中各點均已收斂.

圖1 松弛操作

2 最短路徑算法

2.1 Dijkstra算法

Dijkstra[14]算法基于貪心策略.首先，每次找到離源點最近的一個頂點，確定源點到該點之間的最短路徑，然后，檢查是否能通過該頂點進行松弛操作，最后，得到源點到其他各個頂點之間的最短路徑.

Dijkstra算法的具體步驟如下:

(1)將圖中所有頂點分為P和Q兩個集合：P是已知源點到其他頂點的最短路徑的頂點集合，Q是未知最短路徑的頂點集合，設(shè)置源點到自身之間的距離為0，源點與能直接到達(dá)的頂點之間的距離為該邊權(quán)值w，同時把源點不能直接到達(dá)的頂點的之間的距離設(shè)置為無窮大；

(2)把源點置于P中，表示已求得源點到自身的最短路徑；

(3)遍歷Q，找出距離源點最近的頂點vi，將頂點vi置于P中，表示以求得源點到頂點vi之間的最短路徑.并考察源點到Q中保留的頂點之間是否能通過源點到vi之間的最短路徑松弛，如果有未收斂的頂點則進行松弛操作；

(4)重復(fù)第(3)步，直至Q為空，算法結(jié)束，求得源點到圖中所有頂點之間的最短路徑.

2.2 Floyd算法

Floyd算法[2]是一種動態(tài)規(guī)劃算法.對于G中包含的邊eij，從任意節(jié)點vi到任意節(jié)點vj的最短路徑d[i，j]只存在兩種可能：(1)直接從 vi到 vj，此時 dij=eij；(2)從 vi經(jīng)過若干個節(jié)點到vj.對于每個節(jié)點vk，檢查dij＞dik+dkj是否成立，若成立，則令dij=dik+dkj[6].由此得到狀態(tài)轉(zhuǎn)移方程:dij=min{dij,dik+dkj}.

Floyd算法的具體步驟如下：

(1)從圖G任意一個節(jié)點vk開始，遍歷圖中所有邊eij，檢查是否滿足dik+dkj＜dij，如果成立，說明從節(jié)點i到節(jié)點k再到節(jié)點j的路徑要短于直接從節(jié)點i到節(jié)點j的路徑，故進行松弛操作，更新dij=dik+dkj；

(2)重復(fù)步驟(1)，直至遍歷完圖中所有節(jié)點，dij中記錄的便是節(jié)點i到節(jié)點j的最短路徑距離.

2.3 Bellman-Ford算法

Bellman-Ford算法[14]通過遞推迭代方式反復(fù)對邊集E中每條邊進行松弛操作，使得源點到其他每個頂點u∈V的最短路徑估計值逐漸逼近其最短距離.Bellman-Ford算法最多有n-1個階段，在每一個階段，都需要循環(huán)遍歷圖中的每一條邊進行松弛操作.在前k個階段結(jié)束后，求得從源點最多經(jīng)過k條邊到達(dá)其他所有頂點的最短路.n-1個階段結(jié)束后，就求得了源點最多經(jīng)過n-1條邊到達(dá)其他頂點的最短路徑.由于最短路徑問題是不包含回路的，所以經(jīng)過n-1條邊得到的最短路徑就是源點到其他頂點的最短路徑的確定值.

Bellman-Ford算法的具體步驟如下：

(1)初始化所有點到源點之間的最短距離.將源點到自身的距離設(shè)置為0，源點到其他點的距離設(shè)置為無窮大（表示不可達(dá)）；

(2)對邊集E中的每條邊進行循環(huán)遍歷，進行松弛操作，循環(huán)最多需進行n-1次；

(3)檢測邊集E中的每一條邊的兩個斷點是否收斂.如果存在未收斂的頂點，則說明圖中存在負(fù)權(quán)回路.

2.4 SPFA算法

SPFA[15]算法采用動態(tài)逼近法，通過控制頂點的松弛順序來優(yōu)化Bellman-Ford算法.在Bellman-Ford算法中，松弛過的頂點順序會影響之后頂點的松弛順序，只有那些在上一次松弛中改變了最短路徑估計值的頂點，才可能引起與該頂點相鄰的頂點最短路徑估計值發(fā)生改變.因此，用一個先進先出的隊列來保存被松弛過的頂點，之后只處理隊列中的頂點，以此來降低算法的時間復(fù)雜度.

SPFA算法的具體步驟如下：(1)初始化，將源點加入隊列;

(2)進行迭代，每次取得隊列的隊首節(jié)點，將所有與隊首節(jié)點相鄰的頂點進行松弛操作，若松弛成功，則查看進行松弛操作的頂點是否在隊列中，若不在將該頂點加入隊列中；

(3)反復(fù)從隊列里取出點來對當(dāng)前最短路徑進行優(yōu)化，直至隊列為空不需要再優(yōu)化為止.

3 最短路徑算法的比較分析

Dijkstra算法中計算兩點之間最短路徑時一共需要兩次循環(huán)，因此時間復(fù)雜度為O(N2).Dijkstra算法適用于稠密圖，并且只能適用于邊權(quán)都為正的圖，不能解決負(fù)權(quán)圖的最短路徑問題.其原因是根據(jù)Dijkstra算法的求解思想，集合Q中與源點之間的距離最近的頂點vi即為源點到該點的最短路徑，但如果圖中有負(fù)權(quán)邊，有可能源點通過其他頂點到達(dá)vi的距離比源點直接到達(dá)頂點vi的距離更小.

Floyd算法的時間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2).對于稠密圖，效率要高于執(zhí)行n次Dijkstra算法，也要高于執(zhí)行n次SPFA算法.Floyd算法適用于多源最短路徑，可以算出任意兩個節(jié)點之間的最短距離，適用于稠密圖，和頂點關(guān)系較為密切，并且可以解決負(fù)權(quán)邊的問題，且編碼較為簡單.但時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù).

Bellman-Ford算法最多需要執(zhí)行n-1次循環(huán)，每次循環(huán)需要遍歷圖中所有邊，因此時間復(fù)雜度為O((n-1)*m)=O(nm)，由于采用邊集數(shù)組存儲邊的信息，Bellman-Ford算法的空間復(fù)雜度為O(m).Bellman-Ford算法可以解決負(fù)權(quán)圖問題，并可以檢查圖中是否含有負(fù)權(quán)回路，適用于稀疏圖和邊的關(guān)系較為密切圖.

SPFA算法的平均時間復(fù)雜度為O(m)，當(dāng)m＜＜n2時，SP-FA算法表現(xiàn)出時間復(fù)雜性上的優(yōu)越.時間復(fù)雜度在最壞情況下也是O(nm).由于采用邊集數(shù)組存儲邊的信息，SPFA算法的空間復(fù)雜度為O(m).SPFA算法的時間效率不穩(wěn)定，對于不同的圖的執(zhí)行時間有很大的差別.最好情況下，每個節(jié)點只入隊一次，這時SPFA算法變?yōu)锽FS廣度優(yōu)先遍歷算法，時間復(fù)雜度為O(m).但是在最壞情況下，每個節(jié)點都入隊n-1次，此時SPFA算法退化為Bellman-Ford算法，時間復(fù)雜度為O(nm).如果某個節(jié)點的入隊次數(shù)超過n次，那么圖中肯定含有負(fù)權(quán)回路.SPFA算法可以解決負(fù)權(quán)圖的最短路徑問題，也可以檢測圖中是否含有負(fù)權(quán)回路，同樣適用于稀疏圖和邊的關(guān)系較為密切圖.

對上述算法進行實驗，比較各算法在不同網(wǎng)絡(luò)圖中的特性.通過實驗得出，不同算法之間有著不同的特性，Dijkstra算法只能適用于邊權(quán)都為正的圖，不能解決負(fù)權(quán)圖的最短路問題，適用于稠密圖，和頂點關(guān)系密切.Dijkstra算法最大的弊端是它無法適應(yīng)有負(fù)權(quán)邊的圖.而Floyd算法、Bellman-Ford算法和SPFA算法都可以解決負(fù)權(quán)問題，其中Floyd算法適用于稠密圖，和頂點關(guān)系較為密切.Bellman-Ford算法和SPFA算法都適用于稀疏圖，和邊的關(guān)系較為密切.這幾種算法的區(qū)別詳見表1.

表1 最短路徑算法比較分析

4 結(jié)論

近年來，隨著復(fù)雜網(wǎng)絡(luò)研究的不斷進步，最短路徑問題作為復(fù)雜網(wǎng)絡(luò)優(yōu)化中應(yīng)用比較廣泛的問題之一，引起了廣大研究學(xué)者的關(guān)注.最短路徑問題的涉及互聯(lián)網(wǎng)通信、交通運輸?shù)榷鄠€應(yīng)用領(lǐng)域，對該問題的研究與分析就具有重要的理論意義和實際意義.本文深入分析了幾種經(jīng)典的最短路徑算法，首先，對這幾種最短路徑算法的核心思想與算法流程進行完整的描述；然后，對這幾種經(jīng)典最短路徑算法進行全面的比較分析通過實驗對比，我們得出SPFA算法不僅適用于負(fù)權(quán)圖，在其他網(wǎng)絡(luò)圖中的實驗結(jié)果中也顯示出較好的性能.

我們的下一步工作，將研究最短路徑的改進算法，推廣最短路徑算法去解決實際應(yīng)用生活中的問題.