歡迎來到天天文庫
瀏覽記錄
ID:57731098
大?。?5.00 KB
頁數:2頁
時間:2020-09-02
《單源最短路徑的貪心算法.doc》由會員上傳分享,免費在線閱讀,更多相關內容在教育資源-天天文庫。
1、二、實習過程:1、貪心算法思想:當一個問題具有最優(yōu)子結構性質時,可用動態(tài)規(guī)劃法求解。但有時用貪心算法會更簡單、更有效。貪心算法總是做出在當前看來最好的選擇,也就是說貪心算法并不從整體最優(yōu)考慮,它所做出的選擇只是在某種意義上的局部最優(yōu)選擇。2、單源最短路徑問題:給定帶權有向圖G=(V,E),其中每條邊的權是非負實數。另外,還給定V中的一個頂點,稱為源。現在要計算從源到其他所有頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。2、解單源最短路徑問題算法:Dijkstra算法是解單源最短路徑的貪心算法。
2、其基本思想是,設置頂點集合S并不斷地做貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時,S中僅含有源。設u是G的某一個頂點,把從源到u且中間只經過S中頂點的路徑稱為從源到u的特殊路徑,并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路徑長度的頂點u,將u添加到S中,同時對數組dist做必要的修改。直到S包含了所有V中的頂點,dist就記錄了從源到所有其他頂點之間的最短路徑長度。4、Dijkstra算法描述:輸入帶權有向圖是G=(V,
3、E),V={1,2,...,n}。頂點v是源。a是一個二維數組,a[i][j]表示邊(i,j)的權。當(i,j)不屬于E時,a[i][j]是一個無窮大的數。publicstaticvoiddijkstra(intv){//單源最短路徑問題的Dijkstra算法intn=dist.length-1;if(v<1
4、
5、v>n)return;boolean[]s=newboolean[n+1];//初始化for(inti=1;i<=n;i++){dist[i]=a[v][i];s[i]=false;if(dist[i]<0)prev[i]
6、=0;elseprev[i]=v;}dist[v]=0;s[v]=true;for(inti=1;i0)){u=j;temp=dist[j];}s[u]=true;for(intj=1;j<=n;j++){if((!s[j])&&(a[u][j]>0)){intnewdist=dist[u]+a[u][j];if(newdist7、[j]8、9、dist[j]==-1){dist[j]=newdist;prev[j]=u;}}}}}三、實習總結:通過本次實習,對貪心算法可求解的問題有了進一步了解,有利于區(qū)分何種情況下用動態(tài)規(guī)劃,何種情況用貪心算法,對確定何時用貪心算法可以得到問題的整體最優(yōu)解提供了幫助,同時也為以后解題帶來便利。
7、[j]
8、
9、dist[j]==-1){dist[j]=newdist;prev[j]=u;}}}}}三、實習總結:通過本次實習,對貪心算法可求解的問題有了進一步了解,有利于區(qū)分何種情況下用動態(tài)規(guī)劃,何種情況用貪心算法,對確定何時用貪心算法可以得到問題的整體最優(yōu)解提供了幫助,同時也為以后解題帶來便利。
此文檔下載收益歸作者所有