兩種最短路徑算法的比較

摘要：Dijkstra算法與Floyd算法是求最短路徑的最常用、也是最有效的兩種方法。通過從多方面對Dijkstra算法與Floyd算法的進行比較、分析，給出這兩種算法的差異及Floyd關鍵部分的程序，并介紹了Dijkstra改進的算法。

關鍵詞：最短路徑；Dijkstra算法；Floyd算法；復雜程度

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)10-20ppp-0c

A Compare between the Two Algorithm for Shortest Path

DENG Chun-yan

(Department of Computer and Information Science， Hechi University， Hechi 546300， China)

Abstract: Dijkstra algorithm and Floyd algorithm are the two most commonly used as well as effective methods to compute the shortest path. In this paper， on the basis of the compare and analysis of Dijkstra algorithm and Floyd algorithm， the differences between the two algorithms in many aspects are shown， besides， the key part of the program by Floyd algorithm is given respectively. Furthermore， an improved algorithm based on Dijkstra algorithm is introduced.

Key words: shortest path; Dijkstra algorithm; Floyd algorithm; complex program

1 引言

最短路徑是最優化重要問題之一，它不僅直接應用于解決生產實踐中的許多問題，如管道的鋪設、線路的安排、廠區的選址和布局、設備的更新等。而且也經常被作為一種基本工具，用于解決其他的最優化問題和預測、決策問題。[1]

所謂最短路徑問題，就是給定一個賦權有向圖。即給了一個有向圖D=(V，E)，對每一個弧a=(vi，vj)，相應地有權重w(a)=wij。又給定D中的兩個頂點vs，vt。設P是D中從vs到vt的一條路徑，定義路徑P的權是P中所有弧的權之和，記為w(P)。最短路徑就是要在所有從vs到vt的路中，求一條權重最小的路徑，即求一條從vs到vt的路徑P0，使w(P0)=Min(w(P0))[2]。

應該注意的是：這里所說的最短路徑問題是廣義的最短路徑。即圖中邊的權重不一定是僅指兩點之間的距離。在經濟活動中，它的含義很豐富，比如可表示收益、成本等。因此有向圖中邊的權重不一定都是大于或等于零，它也可能是小于零的數。關于最短路徑算法的研究，目前已有很多的算法，但它們基本上都是以Dijkstra算法、Floyd算法這兩種算法為基礎。因此有必要對Dijkstra算法、Floyd算法作本質的研究。

2 基本思想的比較

2.1 Dijkstra算法的基本思想是：以vs為起點，從圖中找出與其距離最短的頂點。假設該點為vi，然后再以vi作為參照點，從余下的頂點中找出與其距離最短的頂點， 依次類推。直到所有的頂點都對比完為止。至止，vs到各頂點的最短距離就已經求出來了。至于具體的最短路徑，常用的方法是“反向追蹤法”。即從終點出發，“順藤摸瓜”找到最短距離上的各個點，按照有向圖的方向，就可以得到最短路徑。

2.2 Floyd算法的基本思想是：從vs到vt的最短路徑是以下各種可能路徑中的長度最小的那條。[3-4]

若存在，則存在路徑{vs，vt}。（路徑中不含有其它頂點）

若，存在，則存在路徑{vs，v1，vt}。（路徑中所含頂點序號不大于1）

若，存在，則存在一條最短路徑{ vs，…v2…vj}。（路徑中所含頂點序號不大于2）

依次類推，則vs到vt的最短路徑應是上述這些路徑中路徑長度最小者。

兩種算法的基本思想不同，導致了兩種算法結果的不同。對于Dijkstra算法而言，其結果是可求出從某一個頂點到其余各頂點的最短路徑。而Floyd算法的結果是可以得出圖中任意兩對頂點之間的最短路徑。而且由于基本思想不同，它們的算法也大相徑庭。下面給出它們算法的具體步驟：

3 算法步驟的比較

3.1 Dijkstra算法的步驟

從Dijkstra算法的基本思想可以得出其算法的步驟如下：

Step1：初始化：把圖中的頂點集V分為兩個集合V1和V2，且兩個集合的交為空集。令V1={vs}，P(vs)=0，其他頂點歸屬于v2，且T(vj)=+∞。

Step2：當V1≠V時，反復按如下進行：

(1)對vj∈V2，若T(vj)> P(vi)+wij，則T(vj)= P(vi)+wij，否則轉向(2)。

(2)令T(vj0)=Min(T(vj1)，T(vj2)，…T(vj))。若這樣的j0有兩個以上，則可任選一個。

(3)令P(vj0)=T(vj0)，將vj0的T標號變成P標號，并令i=i+1。

Step3：當V1=V時，整個計算過程終止。此時每個vj∈V1，dsj= P(vj)，再用“反向追蹤”方法求出具體的最短路徑。

3.2 Floyd算法的步驟

從Floyd算法的基本思想可以得出其算法的步驟如下：

Step1：初始化距離矩陣D(0)=(dij(0))、序號矩陣S(0)=(sij(0))和執行次數變量k的值。其中距離矩陣D(0)和序號矩陣S(0)分別定義為：

若vi鄰接到vj，則dij(0)= wij；否則dij(0)= ∞。

sij(0)=j (i，j=1，2…n)，即元素sij(0)的值等于它所在的列數。圖中頂點的個數為n。

k=1

Step2：當k≤n時，D(k)中第k行與第k列元素保持與D(k-1)的相應元素相同。其他元素按下式進行計算：

dij(k))=Min(dij(k-1)， dik(k-1))+ dkj(k-1))

序號矩陣S(0)的元素取值規則為：

若dij(k))= dij(k-1)，則sij(k)= sij(k-1)；若dij(k))

經過計算，若dii(k)<0，則結束整個過程的計算。說明圖中存在一條含有頂點vi的負回路，由序號矩陣中的sij(k)可以找出此回路，否則k=k+1，再執行Step2。

Step3：當k=n時，終止整個過程的計算。若dii(k)=+∞，則說明D中不存在從vs到vt的最短路徑；否則dij(k)的值就是vi到vj的最短距離。其相應的路徑可由序號矩陣中的sik(k)找出。(i，j=1，2…n)

從以上介紹的具體算法中可以看出：Floyd算法是從鄰接矩陣出發，而且最短路徑可以從序號矩陣中找出來。最短路徑的權值從距離矩陣中得出。

3.3 相關程序

如果從算法的基本思想及具體的步驟來看，Dijktra算法比Floyd算法更通俗易懂些，也更易于掌握些。而Floyd算法則不具有這些優點，但Floyd算法也有它強勁的優勢。即它除了能求出圖中任意兩對頂點的最短距離和最短路徑外。對于用計算機來實現，它比Dijkstra算法更容易實現多。Floyd算法的編程，用任何一門語言均可實現，如用最基本VB、VF都能實現。而Dijkstra算法的編程，非VB、VF能解決，它需要用c++或者其他更高級的語言。這就要求使用者有相當高的編程能力。

下面給出用VB編寫的floyd算法關鍵部分的程序[5]：

Fork=1ton

Fori=1ton

Forj=1ton

Ifi=kThen

Forc=1to n

dkc(k)= dkc(k-1)# D(k)中第k行與與D(k-1)的第k行的元素對應相同

dck(k)= dck(k-1)# D(k)中第k列與與D(k-1)的第k列的元素對應相同

Next

Else

If j≠kThendij(k))=Min(dij(k-1)， dik(k-1))+ dkj(k-1))

If dij(k))= (dij(k-1) Then

sij(k)= sij(k-1)

Else

sij(k)= sik(k)

End

End

Next

Next

Next

該算法的時間復雜性為O(n3+n2)。

因Dijkstra算法的程序用VB難以實現，故在此不能出。但從它的具體步驟可以看出它的時間復雜度為2n(n-1)。

盡管Floyd算法的時間復雜性與儲蓄空間都比Dijkstra算法的大，但就今天的計算機性能而言，這已不值一提了。作為用戶來說，在選擇算法時，除了考慮所求問題的要求外，還要考慮自己的編程能力。

前面已提到最短路徑問題是廣義的最短路徑，因此在許多情況下，圖中的權重可能是負值。Dijkstra算法要求每一個權重必須大于或等于零，這是該算法的最大局限。為了彌補Dijkstra算法的不足，近年來，已出現Dijkstra算法的改進版。即在出現負值的權重時，用另外一種Dijkstra算法[1]?，F介紹如下：

為方便起見，不妨設任兩點vi、vj都有一條邊。如果兩個頂點之間沒有邊，則給它們添加一條邊，并令wij==+∞。從vs到vj的最短路徑總是從vs出發，沿著一條路到某個點vi，再沿(vi，vj)到vj，從vs到vj的這條路是從vs到vj的最短路徑，因此d(vi，vj)必須滿足如下方程：

d(vi，vj)=Min(d(vi，vj)+wij) i變化

為求解上面的方程，可用如下公式進行計算：

開始時，令d(1)(vs，vj)=wsj， 當t=2，3…n時，d(t)(vi，vj)=Min(d(t-1)(vs，vi)+wij)， j=1，2…n。

若進行到某一步，比如是第k步，對所有j=1，2…n，有d(k)(vs，vj)= d(k-1)(vs，vj)，則{d(k)(vs，vj)}， j=1，2…n，即為從vs到各點的最短距離。

4 結束語

在優化、預測與決策中，最短路徑是常常遇到的。它也是這兩個研究方向中的一個重要問題之一。有關它的求解方法，目前已有多種方法，但那些方法都是以D算法或F算法為基礎，在此基礎上進行一些改進。本質上不同的算法目前尚未出現。作這普通用戶來說，因D算法和F算法各有千秋，在決定選擇方法時，應注意它們的差異和要求。

參考文獻：

[1]《運籌學》教材編寫組．運籌學[M]. 清華大學出版社，2006.7.

[2]程理民， 吳江， 張玉林．運籌學模型與方法教程[M]. 清華大學出版社，2005.9.

[3]李洪波， 王茂波．Floyd最短路徑算法的動態優化[M]. 計算機工程與應用，2006.34:61.

[4]王蘇男．最短路徑算法的比較[M]. 系統工程與電子技術，1994.5:43-49.

[5]蘇國彬．Visual Basic.Net程序設計基礎[M]. 機械出版社，2002.2.

收稿日期：2008-03-04

作者簡介：鄧春燕（1971-）， 女，壯族，廣西河池人，講師，碩士在讀，研究方向：數據挖掘、粗糙集理論與方法。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>