資源描述：
《實(shí)驗(yàn)1貪心法求解單源最短路徑問題.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、實(shí)驗(yàn)1.貪心法求解單源最短路徑問題實(shí)驗(yàn)內(nèi)容本實(shí)驗(yàn)要求基于算法設(shè)計(jì)與分析的一般過程（即待求解問題的描述、算法設(shè)計(jì)、算法描述、算法正確性證明、算法分析、算法實(shí)現(xiàn)與測試）。應(yīng)用貪心策略求解有向帶權(quán)圖的單源最短路徑問題。實(shí)驗(yàn)?zāi)康膗通過本次實(shí)驗(yàn)，掌握算法設(shè)計(jì)與分析的一般過程，以及每個(gè)步驟的基本方法。并應(yīng)用貪心法求解單源最短路徑問題。環(huán)境要求對于環(huán)境沒有特別要求。對于算法實(shí)現(xiàn)，可以自由選擇C,C++,Java，甚至于其他程序設(shè)計(jì)語言。實(shí)驗(yàn)步驟步驟1：理解問題，給出問題的描述。步驟2：算法設(shè)計(jì)，包括策略與數(shù)據(jù)結(jié)構(gòu)的選擇步驟3：描述算法。希望采用源代碼以外
2、的形式，如偽代碼、流程圖等；步驟4：算法的正確性證明。需要這個(gè)環(huán)節(jié)，在理解的基礎(chǔ)上對算法的正確性給予證明；步驟5：算法復(fù)雜性分析，包括時(shí)間復(fù)雜性和空間復(fù)雜性；步驟6：算法實(shí)現(xiàn)與測試。附上代碼或以附件的形式提交，同時(shí)貼上算法運(yùn)行結(jié)果截圖;步驟7：技術(shù)上、分析過程中等各種心得體會與備忘，需要言之有物。說明：步驟1-6在“實(shí)驗(yàn)結(jié)果”一節(jié)中描述，步驟7在“實(shí)驗(yàn)總結(jié)”一節(jié)中描述。實(shí)驗(yàn)結(jié)果1.問題描述給定一個(gè)有向帶全圖G=（V，E），其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外，給定V中的一個(gè)頂點(diǎn)，稱為源點(diǎn)?，F(xiàn)在要計(jì)算源點(diǎn)到所有其他各個(gè)頂點(diǎn)的最短路徑長度，這里的
3、路徑長度是指路徑上所有經(jīng)過邊的權(quán)值之和。這個(gè)問題通常稱為單源最短路徑問題。2.（1)Dijkstra算法思想按各個(gè)結(jié)點(diǎn)與源點(diǎn)之間路徑長度的非減次序，生成源點(diǎn)到各個(gè)結(jié)點(diǎn)的最短路徑的方法。即先求出長度最短的一條路徑，再參照它求出長度次短的一條路徑。依此類推，直到從源點(diǎn)到其它各結(jié)點(diǎn)的最短路徑全部求出為止。1959年提出的，但當(dāng)時(shí)并未發(fā)表。因?yàn)樵谀莻€(gè)年代，算法基本上不被當(dāng)做一種科學(xué)研究的問題。（2）Dijkstra算法設(shè)計(jì)集合S與V-S的劃分：假定源點(diǎn)為u。集合S中的結(jié)點(diǎn)到源點(diǎn)的最短路徑的長度已經(jīng)確定，集合V-S中所包含的結(jié)點(diǎn)到源點(diǎn)的最短路徑的長度
4、待定。特殊路徑：從源點(diǎn)出發(fā)只經(jīng)過S中的結(jié)點(diǎn)到達(dá)V-S中的結(jié)點(diǎn)的路徑。貪心策略：選擇特殊路徑長度最短的路徑，將其相連的V-S中的結(jié)點(diǎn)加入到集合S中。3、描述算法Dijkstra算法的偽代碼：DIJKSTRA(G,w,s)INITIALIZE-SINGLE-SOURCE(G,s)S=ΦQ=G.V//V-S中的結(jié)點(diǎn)按特殊路徑長度非減排序whileQ≠Φu=EXTRACT-MIN(Q)S=S∪{u}foreachv∈G.Adj[u]RELAX(u,v,w)4、Dijkstra算法的求解步驟：步驟1：設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)。帶權(quán)鄰接矩陣C記錄結(jié)點(diǎn)之間的權(quán)
5、值，數(shù)組dist來記錄從源點(diǎn)到其它頂點(diǎn)的最短路徑長度，數(shù)組p來記錄最短路徑。u為源點(diǎn)；步驟2：初始化。令集合S={u}，對于集合V-S中的所有頂點(diǎn)x，設(shè)置dist[x]=C[u][x]。如果頂點(diǎn)x與源點(diǎn)相鄰，設(shè)置p[x]=u；否則，p[x]=-1；步驟3：貪心選擇結(jié)點(diǎn)。在集合V-S中依照貪心策略來尋找使得dist[x]具有最小值的頂點(diǎn)t，t就是集合V-S中距離源點(diǎn)u最近的頂點(diǎn)。步驟4：更新集合S和V-S。將頂點(diǎn)t加入集合S中，同時(shí)更新集合V-S；步驟5：判斷算法是否結(jié)束。如果集合V-S為空，算法結(jié)束。否則，轉(zhuǎn)步驟6；步驟6：對相關(guān)結(jié)點(diǎn)做松弛
6、處理。對集合V-S中的所有與頂點(diǎn)t相鄰的頂點(diǎn)x，如dist[x]>dist[t]+C[t][x]，則dist[x]=dist[t]+C[t][x]并設(shè)置p[x]=t。轉(zhuǎn)步驟3。5、Dijkstra算法的正確性證明–貪心選擇性質(zhì)：采用歸納法。當(dāng)S={s,p}時(shí)，則除源結(jié)點(diǎn)s之外的所有結(jié)點(diǎn)中，結(jié)點(diǎn)p到源點(diǎn)s的距離最短。這是顯然的。假設(shè)當(dāng)S={s,p1,…,pk}時(shí)，即k個(gè)結(jié)點(diǎn)p1,…,pk到源點(diǎn)s的距離最短。當(dāng)S={s,p1,…,pk,pk+1}時(shí)，很顯然結(jié)點(diǎn)pk+1到源點(diǎn)s的距離是最短的。需證明：此時(shí)結(jié)點(diǎn)p1,…,pk到源點(diǎn)s的距離仍然是最短
7、的。用反證法假設(shè)當(dāng)結(jié)點(diǎn)pk+1加入到S后，pi結(jié)點(diǎn)經(jīng)由結(jié)點(diǎn)pk+1到源點(diǎn)s的距離更短，即d(s,pk+1)+d(pk+1,pi)8、總結(jié)Dijkstra算法采用貪心策略，按各個(gè)頂點(diǎn)與源點(diǎn)之間路徑長度遞增的次序，生成源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑方法。先求出長度最短的一條路徑，在參照它求出長度次短的一條路徑，以此類推
