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