幾種經典的最短路徑算法比較分析

趙衛績，鞏占宇，王 雯，樊守芳

（綏化學院 信息工程學院，黑龍江 綏化 152061）

0 前言

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

1 相關定義

1.1 圖

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

1.2 最短路徑

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

1.3 松弛

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

圖1 松弛操作

2 最短路徑算法

2.1 Dijkstra算法

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

Dijkstra算法的具體步驟如下:

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

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

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

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

2.2 Floyd算法

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

Floyd算法的具體步驟如下：

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

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

2.3 Bellman-Ford算法

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

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

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

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

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

2.4 SPFA算法

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

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

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

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

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

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

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

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

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

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

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

4 結論

近年來，隨著復雜網絡研究的不斷進步，最短路徑問題作為復雜網絡優化中應用比較廣泛的問題之一，引起了廣大研究學者的關注.最短路徑問題的涉及互聯網通信、交通運輸等多個應用領域，對該問題的研究與分析就具有重要的理論意義和實際意義.本文深入分析了幾種經典的最短路徑算法，首先，對這幾種最短路徑算法的核心思想與算法流程進行完整的描述；然后，對這幾種經典最短路徑算法進行全面的比較分析通過實驗對比，我們得出SPFA算法不僅適用于負權圖，在其他網絡圖中的實驗結果中也顯示出較好的性能.

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