單源最短路徑問題

《單源最短路徑問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、單源最短路徑問題所謂單源最短路徑問題是指：已知圖G＝（V，E），我們希望找出從某給定的源結(jié)點S∈V到V中的每個結(jié)點的最短路徑。首先，我們可以發(fā)現(xiàn)有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那么，從vs沿P到vi的路是從vs到vi的最短路。（一）Dijkstra算法對于圖G，如果所有Wij≥0的情形下，目前公認的最好的方法是由Dijkstra于1959年提出來的。例1已知如下圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條單行線所需要的費用，現(xiàn)在某人要從v1出發(fā)，通過這個交通網(wǎng)到v8去，求使總費用最小的旅行路線

2、。Dijkstra方法的基本思想是從vs出發(fā)，逐步地向外探尋最短路。執(zhí)行過程中，與每個點對應，記錄下一個數(shù)(稱為這個點的標號)，它或者表示從vs到該點的最短路的權(稱為P標號)、或者是從vs到該點的最短路的權的上界(稱為T標號)，方法的每一步是去修改T標號，并且把某一個具T標號的改變?yōu)榫逷標號的點，從而使G中具P標號的頂點數(shù)多一個，這樣至多經(jīng)過n-1(n為圖G的頂點數(shù))步，就可以求出從vs到各點的最短路。在敘述Dijkstra方法的具體步驟之前，以例1為例說明一下這個方法的基本思想。例1中，s=1。因為所有Wij≥0，故有d(v1,

3、v1)=0。這時，v1是具P標號的點。現(xiàn)在考察從v1發(fā)出的三條弧，(v1,v2),(v1,v3)和(v1,v4)。如果某人從v1出發(fā)沿(v1,v2)到達v2，這時需要d(v1,v1)+w12=6單位的費用；如果他從v1出發(fā)沿(v1,v3)到達v3，這時需要d(v1,v1)+w13=3單位的費用；類似地，若沿(v1,v4)到達v4，這時需要d(v1,v1)+w14=1單位的費用。因為min{d(v1,v1)+w12，d(v1,v1)+w13，d(v1,v1)+w14}=d(v1,v1)+w14=1，可以斷言，他從v1到v4所需要的最小

4、費用必定是1單位，即從v1到v4的最短路是(v1,v4)，d(v1,v4)=1。這是因為從v1到v4的任一條路P，如果不是(v1,v4)，則必是先從v1沿(v1,v2)到達v2，或者沿(v1,v3)到達v3。但如上所說，這時他已需要6單位或3單位的費用，不管他如何再從v2或從v3到達v4，所需要的總費用都不會比1小(因為所有wij≥0)。因而推知d(v1,v4)=1，這樣就可以使v4變成具P標號的點?，F(xiàn)在考察從v1及v4指向其余點的弧，由上已知，從v1出發(fā)，分別沿(v1,v2)、(v1,v3)到達v2,v3，需要的費用分別為6與3，

5、而從v4出發(fā)沿(v4,v6)到達v6所需的費用是d(v1,v4)+w46=1+10=11單位。因min{d(v1,v1)+w12，d(v1,v1)+w13，d(v1,v4)+w46}=d(v1,v1)+w13=3?；谕瑯拥睦碛煽梢詳嘌?，從v1到v3的最短路是(v1,v3)，d(v1,v3)=3。這樣又可以使點v3變成具P標號的點，如此重復這個過程，可以求出從v1到任一點的最短路。在下述的Dijstra方法具體步驟中，用P，T分別表示某個點的P標號、T標號，si表示第i步時，具P標號點的集合。為了在求出從vs到各點的距離的同時，也求

6、出從Vs到各點的最短路，給每個點v以一個λ值，算法終止時λ(v)=m，表示在Vs到v的最短路上，v的前一個點是Vm；如果λ(v)=∞，表示圖G中不含從Vs到v的路；λ(Vs)=0。Dijstra方法的具體步驟：{初始化}i=0S0={Vs}，P(Vs)=0λ(Vs)=0對每一個v<>Vs，令T(v)=+∞，λ(v)=+∞，k=s{開始}①如果Si=V，算法終止，這時，每個v∈Si，d(Vs,v)=P(v)；否則轉(zhuǎn)入②②考察每個使(Vk,vj)∈E且vjSi的點vj。如果T(vj)>P(vk)+wkj，則把T(vj)修改為P(vk)+

7、wkj，把λ(vj)修改為k。③令如果，則把的標號變?yōu)镻標號，令，k=ji，i=i+1，轉(zhuǎn)①，否則終止，這時對每一個v∈Si，d(vs,v)=P(v)，而對每一個。源程序://////////////////////////////////////////////////////////////Graph.h#pragmaonce#definemaxPoint100classCGraph{public:CGraph(void);~CGraph(void);boolSetGraph(doubleg[maxPoint][maxPoint

8、],intstartPoint,intsize);boolDijkstra();voidDisplay();intGetStartPoint();doubleGetBestWay(intdest,intpath[],int&pathL