貪心算法和分支限界法解決單源最短路徑.doc

《貪心算法和分支限界法解決單源最短路徑.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、單源最短路徑計(jì)科1班朱潤(rùn)華2012040732方法1：貪心算法一、貪心算法解決單源最短路徑問(wèn)題描述：?jiǎn)卧醋疃搪窂矫枋觯航o定帶權(quán)有向圖G=(V,E),其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱(chēng)之為源(origin)。現(xiàn)在要計(jì)算從源到其他各頂點(diǎn)的最短路徑的長(zhǎng)度。這里的路徑長(zhǎng)度指的是到達(dá)路徑各邊權(quán)值之和。Dijkstra算法是解決單源最短路徑問(wèn)題的貪心算法。Dijkstra算法的基本思想是：設(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來(lái)擴(kuò)充集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源點(diǎn)到該頂點(diǎn)的最短路徑長(zhǎng)度已知。貪心擴(kuò)充就

2、是不斷在集合S中添加新的元素（頂點(diǎn)）。初始時(shí)，集合S中僅含有源(origin)一個(gè)元素。設(shè)curr是G的某個(gè)頂點(diǎn)，把從源到curr且中間只經(jīng)過(guò)集合S中頂點(diǎn)的路稱(chēng)之為從源到頂點(diǎn)curr的特殊路徑，并且使用數(shù)組distance記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短路徑的長(zhǎng)度。Dijkstra算法每次從圖G中的(V-S)的集合中選取具有最短路徑的頂點(diǎn)curr，并將curr加入到集合S中，同時(shí)對(duì)數(shù)組distance進(jìn)行必要的修改。一旦S包含了所有的V中元素，distance數(shù)組就記錄了從源(origin)到其他頂點(diǎn)的最短路徑長(zhǎng)度

3、。二、貪心算法思想步驟：Dijkstra算法可描述如下，其中輸入帶權(quán)有向圖是G=(V,E)，V={1,2,…，n}，頂點(diǎn)v是源。c是一個(gè)二維數(shù)組，c[i][j]表示邊(i,j)的權(quán)。當(dāng)(i,j)不屬于E時(shí)，c[i][j]是一個(gè)大數(shù)。dist[i]表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長(zhǎng)度。在Dijkstra算法中做貪心選擇時(shí)，實(shí)際上是考慮當(dāng)S添加u之后，可能出現(xiàn)一條到頂點(diǎn)的新的特殊路，如果這條新特殊路是先經(jīng)過(guò)老的S到達(dá)頂點(diǎn)u,然后從u經(jīng)過(guò)一條邊直接到達(dá)頂點(diǎn)i，則這種路的最短長(zhǎng)度是dist[u]+c[u][i]。如果

4、dist[u]+c[u][i]上的權(quán)值。設(shè)S為已知最短路徑的終點(diǎn)的集合,它的初始狀態(tài)為空集。從源點(diǎn)v經(jīng)過(guò)S到圖上其余各點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度的初值為：dist[i]=c[v][i],vi屬于V；2、選擇vu,使得dist[u]=Min{dist[i]

5、vi屬于V-S},vj就是長(zhǎng)度最短的最短路徑的終點(diǎn)。令S=SU{u}；3、修改從v到集合V-S上任一頂點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度:如

6、果dist[u]+c[u][j]#include#include#includeusingnamespacestd;constintN=5;constintM=1000;ifstreamfin("4d5.txt");templatevoidDijkstra(intn,intv,

7、Typedist[],intprev[],Typec[][N+1]);voidTraceback(intv,inti,intprev[]);//輸出最短路徑v源點(diǎn)，i終點(diǎn)intmain(){intv=1;//源點(diǎn)為1intdist[N+1],prev[N+1],c[N+1][N+1];cout<<"有向圖權(quán)的矩陣為："<>c[i][j];cout<

8、tra(N,v,dist,prev,c);for(inti=2;i<=N;i++){cout<<"源點(diǎn)1到點(diǎn)"<voidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];for(inti=1;i<=n;i++){dist[i]=c[v][i];//

9、dist[i]表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長(zhǎng)度s[i]=false;if(dist[i]==M){prev[i]=0;//記錄從源到頂點(diǎn)i的最短路徑i的前一個(gè)頂點(diǎn)}else{prev[i]=v;}}dist[v]=0;s[v]=true;for(inti=1;i