單源最短路徑問題

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

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

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

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

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

5、而從v4出發(fā)沿(v4,v6)到達(dá)v6所需的費(fèi)用是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。這樣又可以使點(diǎn)v3變成具P標(biāo)號(hào)的點(diǎn)，如此重復(fù)這個(gè)過程，可以求出從v1到任一點(diǎn)的最短路。在下述的Dijstra方法具體步驟中，用P，T分別表示某個(gè)點(diǎn)的P標(biāo)號(hào)、T標(biāo)號(hào)，si表示第i步時(shí)，具P標(biāo)號(hào)點(diǎn)的集合。為了在求出從vs到各點(diǎn)的距離的同時(shí)，也求

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

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

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