實驗1貪心法求解單源最短路徑問題

《實驗1貪心法求解單源最短路徑問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實驗1?貪心法求解單源最短路徑問題實驗內(nèi)容木實驗要求基于算法設(shè)計與分析的一般過程(即待求解問題的描述、算法設(shè)計、算法描述、算法正確性證明、算法分析、算法實現(xiàn)與測試)。應(yīng)用貪心策略求解有向帶權(quán)圖的單源最短路徑問題。實驗?zāi)康?通過本次實驗，掌握算法設(shè)計與分析的一?般過程，以及每個步驟的基本方法。并應(yīng)用貪心法求解單源最短路徑問題。環(huán)境要求對于環(huán)境沒有特別要求。對于算法實現(xiàn)，可以白由選擇C,C++,Java,冥至于其他程序設(shè)計語言。實驗步步驟1：理解問題，給出問題的描述。步驟2：算法設(shè)計，包括策略與數(shù)據(jù)結(jié)構(gòu)的選擇步

2、驟3：描述算法。希望采用源代碼以外的形式，如偽代碼、流程圖等；步驟4：算法的正確性證明。需要這個環(huán)節(jié)，在理解的基礎(chǔ)上對算法的正確性給了證明;步驟5：算法復(fù)雜性分析，包括時間復(fù)雜性和空間復(fù)雜性；步驟6：算法實現(xiàn)與測試。附上代碼或以附件的形式提交，同時貼上算法運行結(jié)果截圖;步驟7：技術(shù)上、分析過程中等各種心得休會與備忘，需要言之有物。說明：步驟1?6在“實驗結(jié)果”一節(jié)屮描述，步驟7在“實驗總結(jié)”一節(jié)屮描述。實驗結(jié)果1?問題描述給定一個有向帶全圖G=(V,E),其中每條邊的權(quán)是一個非負(fù)實數(shù)。另外，給定V中的一個頂

3、點，稱為源點?，F(xiàn)在要計算源點到所有其他各個頂點的最短路徑長度，這里的路徑長度是指路徑上所有經(jīng)過邊的權(quán)值之和。這個問題通常稱為單源最短路徑問題。2.(l)Dijkstra算法思想按各個結(jié)點與源點之間路徑長度的非減次序，生成源點到各個結(jié)點的最短路徑的方法。即先求出長度最短的一條路徑，再參照它求出長度次短的一條路徑。依此類推，肓到從源點到其它各結(jié)點的最短路徑全部求出為止。1959年捉出的，但當(dāng)時并未發(fā)表。因為在那個年代，算法基本上不被當(dāng)做一種科學(xué)研究的問題。(2)Dijkstra算法設(shè)計集合sAiv-s的劃分：假

4、定源點為u。集合s中的結(jié)點到源點的最短路徑的長度已經(jīng)確定，集合v-s中所包含的結(jié)點到源點的最短路徑的長度待定。特殊路徑：從源點出發(fā)只經(jīng)過s中的結(jié)點到達(dá)v-s中的結(jié)點的路徑。貪心策略：選擇特殊路徑長度最短的路徑，將其相連的v-s-p的結(jié)點加入到集合s中。3、描述算法Dijkstra算法的偽代碼：DIJKSTRA(G,w,s)INITIALIZE-SINGLE-SOURCE(G,s)S=OQ=G.V//V-S中的結(jié)點按特殊路徑長度非減排序whileQ工①u=EXTRACT-MIN(Q)S=SU{u)foreac

5、hvEG.AdjLuJRELAX(u,v,w)4、Dijkstra算法的求解步驟：步驟1：設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)。帶權(quán)鄰接矩陣C記錄結(jié)點Z間的權(quán)值，數(shù)組dist來記錄從源點到其它頂點的最短路徑長度，數(shù)組P來記錄最短路徑。U為源點；步驟2：初始化。令集合S={u},對于集合V?S中的所有頂點x,設(shè)置dist[x]=C[u][x]o如果頂點x與源點相鄰,設(shè)置p[x]=u；否則,p[x]=-l；步驟3：貪心選擇結(jié)點。在集合V-S中依照貪心策略來尋找使得dist[x]具冇最小值的頂點t,t就是集合V-S中距離源點u最近

6、的頂點。步驟4：更新集合S和V?S。將頂點t加入集合S中，同時更新集合V?S；步驟5：判斷算法是否結(jié)束。如果集合V?S為空，算法結(jié)束。否則，轉(zhuǎn)步驟6；步驟6：對相關(guān)結(jié)點做松弛處理。對集合V-S屮的所有與頂點t和鄰的頂點x,如dist[x]>dist[t]+C[t][x],則dist[x]=dist[t]+C[t][x]并設(shè)置p[x]=to轉(zhuǎn)步驟3。5、Dijkstra算法的正確性證明-貪心選擇性質(zhì)：采川歸納法。當(dāng)S={s,p}時，貝IJ除源結(jié)點s之外的所有結(jié)點屮，結(jié)點P到源點s的距離最短。這是顯然的。假設(shè)當(dāng)

7、S={s,pl,…,pk}時，即k個結(jié)點pl,…,pk到源點s的距離最短。當(dāng)S={s,pl,…,pk,pk+1}時,很顯然結(jié)點pk+1到源點s的距離是最短的。需證明：此時結(jié)點pl,…,pk到源點s的距離仍然是最短的。用反證法假設(shè)當(dāng)結(jié)點pk+1加入到S后，pi結(jié)點經(jīng)由結(jié)點pk+1到源點s的距離更短,即d(s,pk+1)+d(pk+l,pi)

8、(logn)；二重循環(huán)的執(zhí)行次數(shù)為(n-l)+(n-2)+???+l=n(n-l)/2,即時間復(fù)朵性為O(n2)。所以，該算法的時間復(fù)雜性為0(n2)o空間復(fù)雜性：優(yōu)先隊列Q的大小為n?l；所以，該算法的空間復(fù)雜性為O(n)。7、算法實現(xiàn)與測試。-口一點接頂鄰入入99999923A*SAI./?./?8-▼■""—_BVA.m+Tr0999516102131999092999?09991299011"9為為為為0