兩種最短路徑算法的比較

1、兩種最短路徑算法的比較最短路徑是最優(yōu)化重要問題之一，它不但直接應用于解決生產實踐中的很多問題，如管道的鋪設、線路的安排、廠區(qū)的選址和布局、設施的更新等。而且也常常被作為一種基本工具，用于解決其他的最優(yōu)化問題和展望、決議問題。所謂最短路徑問題，就是給定一個賦權有向圖。即給了一個有向圖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.1Dijkstra算法的基本是：以vs為起點，從圖中找出與其距離最短的極點。假定該點為vi，此后再以vi作為參照點，從余下的極點中找出與其距離最短的極點，依次類推。直到所有的極點都比較完為止

3、。至止，vs到各極點的最短距離就已經求出來了。至于詳細的最短路徑，常用的方法是“反向追蹤法”。即從終點出發(fā)，“順藤摸瓜”找到最短距離上的各個點，依照有向圖的方向，就能夠獲取最短路徑。2.2Floyd算法的基本思想是：從vs到vt的最短路徑是以下各樣可能路徑中的長度最小的那條。3-4若存在，則存在路徑vs，vt。（路徑中不含有其他極點）若，存在，則存在路徑vs，v1，vt。（路徑中所含極點序號不大于1）若，存在，則存在一條最短路徑vs,v2vj。（路徑中所含極點序號不大于2）依次類推，則vs到vt的最短路徑應是上述這些路徑中路徑長度最小者。兩種算法的基本思想不一樣樣，以致了兩種算法結果的不一樣樣

4、。對于Dijkstra算法而言，其結果是可求出從某一個極點到其他各極點的最短路徑。而Floyd算法的結果是能夠得出圖中隨意兩對極點之間的最短路徑。而且由于基本思想不一樣樣，它們的算法也大相徑庭。下面給出它們算法的詳細步驟：算法步驟的比較3.1Dijkstra算法的步驟從Dijkstra算法的基本思想能夠得出其算法的步驟以下：Step1：初始化：把圖中的極點集V分為兩個會合V1和V2，且兩個會合的交為空集。令V1=vs，P(vs)=0，其他極點歸屬于v2，且T(vj)=+。Step2：當V1V時，頻頻按以下進行：(1)對vjV2，若T(vj)P(vi)+wij，則T(vj)=P(vi)+wij，

5、否則轉向(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時，整個計算過程停止。此時每個vjV1，dsj=P(vj)，再用“反向追蹤”方法求出詳細的最短路徑。3.2Floyd算法的步驟從Floyd算法的基本思想能夠得出其算法的步驟以下：Step1：初始化距離矩陣D(0)=(dij(0)、序號矩陣S(0)=(sij(0)和履行次數變量k的值。其中距離矩陣D(0)和序號矩陣S(0)分別定義為：若vi毗鄰到vj，則dij(0)=wij

6、；否則dij(0)=。sij(0)=j(i,j=1,2，即元n)素sij(0)的值等于它所在的列數。圖中極點的個數為n。k=1Step2：當kn時，D(k)中第k行與第k列元素保持與D(k-1)的相應元素相同。其他元素按下式進行計算：dij(k)=Min(dij(k-1),dik(k-1)+dkj(k-1)序號矩陣S(0)的元素取值規(guī)則為：若dij(k)=dij(k-1)，則sij(k)=sij(k-1)；若dij(k)dij(k-1)，則sij(k)=sik(k)。經過計算，若dii(k)0，則結束整個過程的計算。說明圖中存在一條含有極點vi的負回路，由序號矩陣中的sij(k)能夠找出此回路

7、，否則k=k+1，再履行Step2。Step3：當k=n時，停止整個過程的計算。若dii(k)=+，則說明D中不存在從vs到vt的最短路徑；否則dij(k)的值就是vi到vj的最短距離。其相應的路徑可由序號矩陣中的sik(k)找出。(i,j=1,2n)從以上介紹的詳細算法中能夠看出：Floyd算法是從毗鄰矩陣出發(fā)，而且最短路徑能夠從序號矩陣中找出來。最短路徑的權值從距離矩陣中得出。3.3有關程序假如從算法的基本思想及詳細的步驟來看，Dijktra算法比Floyd算法更平時易懂些，也更易于掌握些。而Floyd算法例不擁有這些優(yōu)點，但Floyd算法也有它激烈的優(yōu)勢。即它除了能求出圖中隨意兩對極點的

8、最短距離和最短路徑外。對于用計算機來實現，它比Dijkstra算法更簡單實現多。Floyd算法的編程，用任何一門語言均可實現，如用最基本VB、VF都能實現。而Dijkstra算法的編程，非VB、VF能解決，它需要用c+或許其他更高級的語言。這就要求使用者有相當高的編程能力。下面給出用VB編寫的floyd算法要點部分的程序：Fork=1tonFori=1tonForj=1tonIfi=kThenForc=1tondkc(k)=dkc(k-1)#D(k)中第k行與與D(k-1)的第k行的元素對應相同dck(k)=dck(k-1)#D(k)中第k列與與D(k-1)的第k列的元素對應相同NextEls

9、eIfjkThendij(k)=Min(dij(k-1),dik(k-1)+dkj(k-1)Ifdij(k)=(dij(k-1)Thensij(k)=sij(k-1)Elsesij(k)=sik(k)EndEndNextNextNext該算法的時間復雜性為O(n3+n2)。因Dijkstra算法的程序用VB難以實現，故在此不可以夠出。但從它的詳細步驟能夠看出它的時間復雜度為2n(n-1)。盡管Floyd算法的時間復雜性與存儲空間都比Dijkstra算法的大，但就今日的計算機性能而言，這已何足道哉了。作為用戶來說，在選擇算法時，除了考慮所求問題的要求外，還要考慮自己的編程能力。前面已提到最短路徑

10、問題是廣義的最短路徑，因此在很多情況下，圖中的權重可能是負值。Dijkstra算法要求每一個權重必須大于或等于零，這是該算法的最大限制。為了填充Dijkstra算法的不足，近來幾年來，已出現Dijkstra算法的改良版。即在出現負值的權重時，用其他一種Dijkstra算法。現介紹以下：為方便起見，不如設任兩點vi、vj都有一條邊。假如兩個頂點之間沒有邊，則給它們增加一條邊，并令wij=+。從vs到vj的最短路徑老是從vs出發(fā)，沿著一條路到某個點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,3n時，d(t)(vi,vj)=Min(d(t-1)(vs,vi)+wij),j=1,2。n若進行到某一步，比方是第k步，對所有j=1,2n，有d(k)(vs,vj)=d(k-1)(vs,vj)，則d(k)(vs,vj),j=1,2n，即為從