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

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

1、單源最短路徑計科1班朱潤華2012040732方法1：貪心算法一、貪心算法解決單源最短路徑問題描述：單源最短路徑描述：給定帶權有向圖G=(V,E),其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱之為源(origin)。現(xiàn)在要計算從源到其他各頂點的最短路徑的長度。這里的路徑長度指的是到達路徑各邊權值之和。Dijkstra算法是解決單源最短路徑問題的貪心算法。Dijkstra算法的基本思想是：設置頂點集合S并不斷地做貪心選擇來擴充集合。一個頂點屬于集合S當且僅當從源點到該頂點的最短路徑長度已知。貪心擴充就

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

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

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

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

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源點，i終點intmain(){intv=1;//源點為1intdist[N+1],prev[N+1],c[N+1][N+1];cout<<"有向圖權的矩陣為："<>c[i][j];cout<

8、tra(N,v,dist,prev,c);for(inti=2;i<=N;i++){cout<<"源點1到點"<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]表示當前從源到頂點i的最短特殊路徑長度s[i]=false;if(dist[i]==M){prev[i]=0;//記錄從源到頂點i的最短路徑i的前一個頂點}else{prev[i]=v;}}dist[v]=0;s[v]=true;for(inti=1;i