單源最短路徑的貪心算法.doc

單源最短路徑的貪心算法.doc

ID:57731098

大?。?5.00 KB

頁數:2頁

時間:2020-09-02

單源最短路徑的貪心算法.doc_第1頁
單源最短路徑的貪心算法.doc_第2頁
資源描述:

《單源最短路徑的貪心算法.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(newdist

7、[j]

8、

9、dist[j]==-1){dist[j]=newdist;prev[j]=u;}}}}}三、實習總結:通過本次實習,對貪心算法可求解的問題有了進一步了解,有利于區(qū)分何種情況下用動態(tài)規(guī)劃,何種情況用貪心算法,對確定何時用貪心算法可以得到問題的整體最優(yōu)解提供了幫助,同時也為以后解題帶來便利。

當前文檔最多預覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數學公式或PPT動畫的文件,查看預覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權有爭議請及時聯系客服。
3. 下載前請仔細閱讀文檔內容,確認文檔內容符合您的需求后進行下載,若出現內容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網絡波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯系客服處理。