兩種最短路徑算法的比較

1、兩種最短路徑算法的比較最短路徑是最優(yōu)化重要問(wèn)題之一，它不但直接應(yīng)用于解決生產(chǎn)實(shí)踐中的很多問(wèn)題，如管道的鋪設(shè)、線(xiàn)路的安排、廠(chǎng)區(qū)的選址和布局、設(shè)施的更新等。而且也常常被作為一種基本工具，用于解決其他的最優(yōu)化問(wèn)題和展望、決議問(wèn)題。所謂最短路徑問(wèn)題，就是給定一個(gè)賦權(quán)有向圖。即給了一個(gè)有向圖D=(V，E)，對(duì)每一個(gè)弧a=(vi,vj)，相應(yīng)地有權(quán)重w(a)=wij。又給定D中的兩個(gè)極點(diǎn)vs，vt。設(shè)P是D中從vs到vt的一條路徑，定義路徑P的權(quán)是P中所有弧的權(quán)之和，記為w(P)。最短路徑就是要在所有從vs到vt的路中，求一條權(quán)重最小的路徑，即求一條從vs到vt的路徑P0，使w(P0)=Min(w(P0)

2、。應(yīng)當(dāng)注意的是：這里所說(shuō)的最短路徑問(wèn)題是廣義的最短路徑。即圖中邊的權(quán)重不用定是僅指兩點(diǎn)之間的距離。在經(jīng)濟(jì)活動(dòng)中，它的含義很豐富，比方可表示利潤(rùn)、成本等。因此有向圖中邊的權(quán)重不用定都是大于或等于零，它也可能是小于零的數(shù)。對(duì)于最短路徑算法的研究，當(dāng)前已有很多的算法，但它們基本上都是以Dijkstra算法、Floyd算法這兩種算法為基礎(chǔ)。因此有必要對(duì)Dijkstra算法、Floyd算法作實(shí)質(zhì)的研究。基本的比較2.1Dijkstra算法的基本是：以vs為起點(diǎn)，從圖中找出與其距離最短的極點(diǎn)。假定該點(diǎn)為vi，此后再以vi作為參照點(diǎn)，從余下的極點(diǎn)中找出與其距離最短的極點(diǎn)，依次類(lèi)推。直到所有的極點(diǎn)都比較完為止

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

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

5、否則轉(zhuǎn)向(2)。(2)令T(vj0)=Min(T(vj1),T(vj2),若。T(vj)這樣的j0有兩個(gè)以上，則可任選一個(gè)。(3)令P(vj0)=T(vj0)，將vj0的T標(biāo)號(hào)變成P標(biāo)號(hào)，并令i=i+1。Step3：當(dāng)V1=V時(shí)，整個(gè)計(jì)算過(guò)程停止。此時(shí)每個(gè)vjV1，dsj=P(vj)，再用“反向追蹤”方法求出詳細(xì)的最短路徑。3.2Floyd算法的步驟從Floyd算法的基本思想能夠得出其算法的步驟以下：Step1：初始化距離矩陣D(0)=(dij(0)、序號(hào)矩陣S(0)=(sij(0)和履行次數(shù)變量k的值。其中距離矩陣D(0)和序號(hào)矩陣S(0)分別定義為：若vi毗鄰到vj，則dij(0)=wij

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

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

8、最短距離和最短路徑外。對(duì)于用計(jì)算機(jī)來(lái)實(shí)現(xiàn)，它比Dijkstra算法更簡(jiǎn)單實(shí)現(xiàn)多。Floyd算法的編程，用任何一門(mén)語(yǔ)言均可實(shí)現(xiàn)，如用最基本VB、VF都能實(shí)現(xiàn)。而Dijkstra算法的編程，非VB、VF能解決，它需要用c+或許其他更高級(jí)的語(yǔ)言。這就要求使用者有相當(dāng)高的編程能力。下面給出用VB編寫(xiě)的floyd算法要點(diǎn)部分的程序：Fork=1tonFori=1tonForj=1tonIfi=kThenForc=1tondkc(k)=dkc(k-1)#D(k)中第k行與與D(k-1)的第k行的元素對(duì)應(yīng)相同dck(k)=dck(k-1)#D(k)中第k列與與D(k-1)的第k列的元素對(duì)應(yīng)相同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該算法的時(shí)間復(fù)雜性為O(n3+n2)。因Dijkstra算法的程序用VB難以實(shí)現(xiàn)，故在此不可以夠出。但從它的詳細(xì)步驟能夠看出它的時(shí)間復(fù)雜度為2n(n-1)。盡管Floyd算法的時(shí)間復(fù)雜性與存儲(chǔ)空間都比Dijkstra算法的大，但就今日的計(jì)算機(jī)性能而言，這已何足道哉了。作為用戶(hù)來(lái)說(shuō)，在選擇算法時(shí)，除了考慮所求問(wèn)題的要求外，還要考慮自己的編程能力。前面已提到最短路徑

10、問(wèn)題是廣義的最短路徑，因此在很多情況下，圖中的權(quán)重可能是負(fù)值。Dijkstra算法要求每一個(gè)權(quán)重必須大于或等于零，這是該算法的最大限制。為了填充Dijkstra算法的不足，近來(lái)幾年來(lái)，已出現(xiàn)Dijkstra算法的改良版。即在出現(xiàn)負(fù)值的權(quán)重時(shí)，用其他一種Dijkstra算法。現(xiàn)介紹以下：為方便起見(jiàn)，不如設(shè)任兩點(diǎn)vi、vj都有一條邊。假如兩個(gè)頂點(diǎn)之間沒(méi)有邊，則給它們?cè)黾右粭l邊，并令wij=+。從vs到vj的最短路徑老是從vs出發(fā)，沿著一條路到某個(gè)點(diǎn)vi，再沿(vi,vj)到vj，從vs到vj的這條路是從vs到vj的最短路徑，因此d(vi,vj)必定滿(mǎn)足以下方程：d(vi,vj)=Min(d(vi,vj)+wij)i變化為求解上面的方程，可用以下公式進(jìn)行計(jì)算：開(kāi)始時(shí)，令d(1)(vs,vj)=wsj,當(dāng)t=2,3n時(shí)，d(t)(vi,vj)=Min(d(t-1)(vs,vi)+wij),j=1,2。n若進(jìn)行到某一步，比方是第k步，對(duì)所有j=1,2n，有d(k)(vs,vj)=d(k-1)(vs,vj)，則d(k)(vs,vj),j=1,2n，即為從