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

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ò)充就是不斷在集合S中添加新的元素（頂點(diǎn)）。初始時(shí)，集合S中僅含有源(origin)

2、一個(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)度。二、 貪心算法思想步驟：Dijkstra算法可描述如下，其中輸入帶權(quán)有向圖是G=(V,E)，V=1,2,，n，頂點(diǎn)v是源。c是一個(gè)二維數(shù)組，cij表示邊(i,j

3、)的權(quán)。當(dāng)(i,j)不屬于E時(shí)，cij是一個(gè)大數(shù)。disti表示當(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)度是distu+cui。如果distu+cui<disti，則需要更新disti的值。步驟如下： 1、用帶權(quán)的鄰接矩陣c來(lái)表示帶權(quán)有向圖, cij表示弧<vi,vj>上的權(quán)值。設(shè)S為已知最短路徑的終點(diǎn)的集合,它的初始狀態(tài)為空集。從源點(diǎn)v經(jīng)過(guò)S到圖上其余各點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度的初值為：di

4、sti=cvi, vi屬于V； 2、選擇vu, 使得distu=Mindisti | vi屬于V-S,vj就是長(zhǎng)度最短的最短路徑的終點(diǎn)。令S=S U u；3、修改從v到集合V-S上任一頂點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度:如果 distu+cuj< distj 則修改 distj= distu+cuj； 4、重復(fù)操作(2),(3)共n-1次。三、 算法實(shí)現(xiàn)代碼：#include <stdafx.h>#include <iostream>#include <fstream>#include <string>using namespace std; co

5、nst int N = 5;const int M = 1000;ifstream fin("4d5.txt"); template<class Type>void Dijkstra(int n,int v,Type dist,int prev,Type cN+1); void Traceback(int v,int i,int prev);/輸出最短路徑 v源點(diǎn)，i終點(diǎn) int main() int v = 1;/源點(diǎn)為1 int distN+1,prevN+1,cN+1N+1; cout<<"有向圖權(quán)的矩陣為："<<

6、;endl; for(int i=1; i<=N; i+) for(int j=1; j<=N; j+) fin>>cij; cout<<cij<<" " cout<<endl; Dijkstra(N,v,dist,prev,c); for(int i=2; i<=N; i+) cout<<"源點(diǎn)1到點(diǎn)"<<i<<"的最短路徑長(zhǎng)度為:"<<disti<<"，其路徑為" Traceback(1

7、,i,prev); cout<<endl; return 0; template<class Type> void Dijkstra(int n,int v,Type dist,int prev,Type cN+1) bool sN+1; for(int i=1; i<=n; i+) disti = cvi;/disti表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長(zhǎng)度 si = false; if(disti = M) previ = 0;/記錄從源到頂點(diǎn)i的最短路徑i的前一個(gè)頂點(diǎn) else previ = v; distv = 0; sv = true; for(int

8、i=1; i<n; i+) int temp = M; int u = v;/上一頂點(diǎn) /取出V-S中具有最短特殊路徑長(zhǎng)度的頂點(diǎn)u for(int j=1; j<=n; j+) if(!sj) && (distj<temp) u = j temp = distj; su = true; /根據(jù)作出的貪心選擇更新Dist值 for(int j=1; j<=n; j+) if(!sj) && (cuj<M) Type newdist = distu + cuj; if(newdist < distj) distj = newdis

9、t; prevj = u; /輸出最短路徑 v源點(diǎn)，i終點(diǎn)void Traceback(int v,int i,int prev) if(v = i) cout<<i; return; Traceback(v,previ,prev); cout<<"->"<<I; 四、計(jì)算復(fù)雜性 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要O(n)時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時(shí)間。算法的其余部分所需要的時(shí)間不超過(guò)O(n2)。五、 運(yùn)行結(jié)果：方法2：分支限

10、界法一、 分支限界法解決單源最短路徑問(wèn)題描述：采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹(shù)的結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱(chēng)為分枝限界法。所謂“分支”是采用廣度優(yōu)先的策略，依次生成擴(kuò)展結(jié)點(diǎn)的所有分支（即：兒子結(jié)點(diǎn)）。所謂“限界”是在結(jié)點(diǎn)擴(kuò)展過(guò)程中，計(jì)算結(jié)點(diǎn)的上界（或下界），邊搜索邊減掉搜索樹(shù)的某些分支，從而提高搜索效率按照廣度優(yōu)先的原則，一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)（E-結(jié)點(diǎn)）R后，算法將依次生成它的全部孩子結(jié)點(diǎn)，將那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子舍棄，其余兒子加入活結(jié)點(diǎn)表中。然后，從活結(jié)點(diǎn)表中取出一個(gè)結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程，直至找到問(wèn)題的解或判定無(wú)解為止。二、 分支限界法算法思想描述：算法從

11、圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開(kāi)始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過(guò)程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。 在算法擴(kuò)展結(jié)點(diǎn)的過(guò)程中，一旦發(fā)現(xiàn)一個(gè)結(jié)點(diǎn)的下界不小于當(dāng)前找到的最短路長(zhǎng)，則算法剪去以該結(jié)點(diǎn)為根的子樹(shù)。在算法中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。從源頂點(diǎn)s出發(fā)，2條不同路徑到達(dá)圖G的同一頂點(diǎn)。由于兩條路徑的路長(zhǎng)不同

12、，因此可以將路長(zhǎng)長(zhǎng)的路徑所對(duì)應(yīng)的樹(shù)中的結(jié)點(diǎn)為根的子樹(shù)剪去。三、 算法實(shí)現(xiàn)代碼：#include "stdafx.h" #include "MinHeap2.h" #include <iostream> #include <fstream> using namespace std; ifstream fin("6d2.txt"); template<class Type> class Graph friend int main(); public: void ShortesPaths(int); pr

13、ivate: int n, /圖G的頂點(diǎn)數(shù) *prev; /前驅(qū)頂點(diǎn)數(shù)組 Type *c, /圖G的領(lǐng)接矩陣 *dist; /最短距離數(shù)組 ; template<class Type> class MinHeapNode friend Graph<Type> public: operator int ()constreturn length; private: int i; /頂點(diǎn)編號(hào) Type length; /當(dāng)前路長(zhǎng) ; template<class Type> void Graph<Type>:ShortesPaths(int v)/單源

14、最短路徑問(wèn)題的優(yōu)先隊(duì)列式分支限界法 MinHeap<MinHeapNode<Type>> H(1000); MinHeapNode<Type> E; /定義源為初始擴(kuò)展節(jié)點(diǎn) E.i=v; E.length=0; distv=0; while (true)/搜索問(wèn)題的解空間 for (int j = 1; j <= n; j+) if (cE.ij!=0)&&(E.length+cE.ij<distj) / 頂點(diǎn)i到頂點(diǎn)j可達(dá)，且滿足控制約束 distj=E.length+cE.ij; prevj=E.i; / 加入活結(jié)點(diǎn)優(yōu)先隊(duì)列

15、MinHeapNode<Type> N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一擴(kuò)展結(jié)點(diǎn) catch (int) break; if (H.currentsize=0)/ 優(yōu)先隊(duì)列空 break; int main() int n=11; int prev12 = 0,0,0,0,0,0,0,0,0,0,0,0; int dist12=1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000; cout<<"單源圖的

16、鄰接矩陣如下："<<endl; int *c = new int*n+1; for(int i=1;i<=n;i+) ci=new intn+1; for(int j=1; j<=n; j+) fin>>cij; cout<<cij<<" " cout<<endl; int v=1; Graph<int> G; G.n=n; G.c=c; G.dist=dist; G.prev=prev; G.ShortesPaths(v); cout<<"從S到T的最短路長(zhǎng)是："<<dist11<<endl; for (int i = 2; i <= n; i+) cout<<"prev("<<i<<")="<<previ<<" "<<endl; for (int i = 2