貪心算法單源最短路徑問題-dijkstra

1、單源最短路徑問題所謂單源最短路徑問題是指：已知圖 G（V，E），到 V 中的每個結(jié)點(diǎn)的最短路徑。希望找出從某給定的源結(jié)點(diǎn) SV首先，可以發(fā)現(xiàn)有這樣一個事實(shí)：如果 P 是 G 中從 vs 到 vj 的最短路，vi 是 P 中的一個點(diǎn)，那么，從 vs 沿 P 到 vi 的路是從 vs 到 vi 的最短路。對于圖 G，如果所有 Wij0 的情形下，目前公認(rèn)的最好的方法是由 Dijkstra 于 1959 年提出來的。Dijkstra 算法基本：設(shè)置頂點(diǎn)集合 S 并不斷地作貪心選擇來擴(kuò)充這個集合。一個頂點(diǎn)屬于集合S 當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知。初始時，S 中僅含有源節(jié)點(diǎn)。設(shè) u 是 G 的

2、某一個頂點(diǎn)，把從源到 u 且中間只經(jīng)過 S 中頂點(diǎn)的路稱為從源到 u 的特殊路徑，用數(shù)組 Di頂點(diǎn) i 當(dāng)前所對應(yīng)的最短特殊路徑長度。（3）Dijkstra 算法每次從 V-S 中取出具有最短特殊路長度的頂點(diǎn) u，將 u 添加到 S 中，同時對數(shù)組 D 作必要的修改。（4）一旦 S 包含了所有 V 中頂點(diǎn)，dist 就源程序 1：/Dijkstra 算法#include #include了從源到所有其它頂點(diǎn)之間的最短路徑長度。using namespatd;#define VEX5/定義結(jié)點(diǎn)的個數(shù)#define maxpo100double graphmaxpo 0 , 10 , -1 , 3

3、0 , 100 , -1 , 0 , 50 , -1 , -1 , -1 , -1 , 0 , -1 , 10 , -1 , -1 , 20 , 0 , 60 , -1 , -1 , -1 , -1 , 0 ; /鄰接矩陣=void main()Rmaxpo=0,Bmaxpo;DVEX,PVEX;/定義數(shù)組 D 用來存放結(jié)點(diǎn)特殊距離，P 數(shù)組存放父親結(jié)點(diǎn)/初始時，紅點(diǎn)集中僅有源結(jié)點(diǎn) 0 R0=1; B0=0;for(Bi=1;i=1;iVEX;i+)/對數(shù)組 D、P 進(jìn)行初始化for(i=0;iVEX;i+)Di=graph0i;if(Di!=-1) Pi=0;els=-1;/輸出鄰接矩陣 f

4、or(i=0;iVEX;i+)for(j=0;jVEX;j+)coutgraphijt;coutendl;/輸出 D、P 表頭cout;for(i=0;iVEX;i+)coutDi;cout;for(i=0;iVEX;i+) coutPicoutendl;for(for(k=1;kVEX;k+)/每次從藍(lán)點(diǎn)集中取出具有最短特殊路長度的結(jié)點(diǎn) minmin=0;Bmin=0;) min+; /求藍(lán)點(diǎn)集結(jié)點(diǎn)最小下標(biāo)元素for(j=min;jVEX;j+)if(Dj!=-1&DjDmin&Bj=1)min=j; coutmin=min;/將具有最短特殊路長度的結(jié)點(diǎn) min 添加到紅點(diǎn)集中Rmin=1;

5、 Bmin=0;/對數(shù)組 D 作必要的修改for(j=1;jDmin+graphminj|Dj=-1)Dj=Dmin+graphminj;/每次迭代求最小值，最后一次即為到源點(diǎn)的最短路徑Pj=min;/輸出最短路徑for(i=0;iVEX;i+) coutDi;cout;for(i=0;iVEX;i+) coutPi coutendl;源程序 2:#includeusing namespatd;/ Graph.h#define maxPo100 class CGraphpublic: CGraph(void);CGraph(void);bool SetGraph( double gmaxPom

6、axPo bool Dijkstra();void Display();GetStartPo(); ,startPo,size );double GetBestWay(private:dest ,path ,&pathLen );bool solved;/標(biāo)志當(dāng)前圖是否已經(jīng)求解double graphmaxPomaxPo;/當(dāng)前圖布局 size;/地圖大小startPo;/起點(diǎn)double distmaxPo;/當(dāng)前圖的解 prevmaxPo;/ Graph.cppCGraph:CGraph(void)for(for(i = 0 ; i maxPo; i+ )j = 0 ; j maxPo;

7、j+ )graphij = -1;startPo size = -1;= -1;solved = false; /當(dāng)前圖還沒有求解CGraph:CGraph(void)/bool CGraph:SetGraph( double gmaxPomaxPo ,startPo,size )for(for(i = 0 ; i size ; i+ )j = 0 ; j startPo= startPo;this-size = size; solved = false; Dijkstra(); return true;/bool CGraph:Dijkstra()bool smaxPo;for(j = 0

8、; j size ; j+ )distj = graphstartPoj; sj = false;if( distj 0 ) /disti0，表示沒有路徑連接prevj = 0; elseprevj = startPo;結(jié)點(diǎn) startPo與結(jié)點(diǎn) j/從起點(diǎn)出發(fā)diststartPo = 0; sstartPo = true;for(i = 0 ; i size ; i+ )double temp;u = startPo; bool flag = false;for(j = 0 ; j 0 & distj temp )u = j;temp = distj;elseu = j;temp = di

9、stj; flag = true;su = true;for( j = 0 ; j 0 )double newDist = distu + graphuj; if( distj 0 | newDist distj )distj = newDist; prevj = u;solved = true; return true;/void CGraph:Display()prf( 當(dāng)前地圖的鄰接矩陣n );for(i = 0 ; i size ; i+ )for(j = 0 ; j size ; j+ )prf( %5.f , graphij );prf( n );/double CGraph:Ge

10、tBestWay(p = dest; thewaymaxPo; len = 0;while( p != startPo)thewaylen = p; p = prevp; len+;thewaylen = startPo; len+;dest ,path ,&pathLen )for(i = 0 , j = len - 1 ; i len ; i+ , j- )pathi = thewayj; pathLen = len;return distdest;/CGraph:GetStartPo()return startPo;/ Dijkstra.cpp : 定義控制臺應(yīng)用程序的voidmain(

11、)double graphmaxPo = 0 , 10 , -1 , 30 , 100 , -1 , 0 , 50 , -1 , -1 , -1 , -1 , 0 , -1 , 10 , -1 , -1 , 20 , 0 , 60 , -1 , -1 , -1 , -1 , 0 ;size = 5;start = 0;點(diǎn)。dest = 1; pathlen; pathmaxPo;double dist;CGraph g;g.SetGraph( graph , start , size ); g.Display();prf( n );for( dest = 0 ; dest size ; dest+ )dist