實驗三最短路徑算法分析與設計

《實驗三最短路徑算法分析與設計》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。

1、西財銓丈聲學生實驗報告學院：軟件與通信工程學院課程名稱：算法分析與設計專業(yè)班級：軟件144班姓名：劉洋學號：0144119學生實驗報告學生姓名劉洋學號0144119同組人實驗項目最短路徑算法分析與設計□必修□選修□演示性實驗□驗證性實驗□操作性實驗□綜合性實驗實驗地點G108實驗儀器臺號指導教師李剛實驗H期及節(jié)次4-89八一、實驗綜述1、實驗目的及要求目的：（1）熟悉不同最短路徑問題的求解的方法與一般技巧；（2）掌握Floyd算法、Dijkstra算法的實現(xiàn)；（3）掌握調試、改進算法程序基木方法；（4）熟悉兩種方法在解決問題屮的應用；要求.?（1）自己生成問

2、題實例；（2）報告不同算法在實驗中的表現(xiàn)。2、實驗儀器、設備或軟件儀器：Windowsxp/7/8/10軟件:vs2013二、實驗過程（實驗步驟、記錄、數(shù)據(jù)、分析）問題實例：利用圖的最短路徑原理為用戶提供路徑咨詢，掌握求最短路徑的算法并編程實現(xiàn)。算法設計思想：弗洛伊德算法是用鄰接矩陣cost表示帶權有向圖。如果從頂點Vi到Vj有弧，則從到Vj存在一條長度為C0St[i][j]的路徑，該路徑不一定是最短路徑，需耍進行n次試探。首先考慮路徑（Vi，VI，Vj）是否存在（即判別?。╲i，vl）（vl，vj）是否存在），如果存在，則比較（Vi,VI，Vj）和（vi,

3、vj）的路徑長度，取較短者為從vi到vj的屮間頂點序號不人于1的最短路徑、在路徑上再增加一個頂點v2，若（vi…，v2）和（v2…vj）分別是當前找到的中間頂點序號不大于1的最短路徑，則（vi..,v2…,vj）就有可能是從vi到vj的中間頂點的序號不大于2的最短路徑。將他和已經得到從vi到vj中間頂點序號不大于1的最短路徑比較，從中選出長度較短者作為從vi到vj中間頂點序號不大于2的最短路徑之后，再增加一個頂點v3,繼續(xù)進行試探，依次類推。在一般情況卜，若（vi…,vk）和（vk…vj）分別是從vi到vk和vk到vj的中間頂點序號不大于k-1的最短路徑，則

4、將（vi…，vk-vj)和已經得到的Vi到vj且中間頂點序號不大于k-1的最短路徑相比較，取其長度較短者作為從Vi到Vj的屮間頂點序號不大于k的最短路徑。如此重復，經過n次比較，最后求的的必是從vi到vj的最短路徑。用此方法，課可同時求的每對頂點間的最短路徑。綜上所述，佛洛依德算法的基木思想是遞推的產生一個矩陣序列：aO,al,…ak?an,其中：aO[i][j]=cost[i][j];Ak[i][j]=min{a(k-l)[i][j],a(k_l)[i][k]+a(k-l)[j][k];}(l〈=k〈=n);由上述公式可以看出，a[i][j]是從Vi到Vj

5、中間頂點序號不大于1的最短路徑長度;ak[i][j]是從Vi到Vj中間頂點序號不大于1的最短路徑長度;an[i][j]是從Vi到Vj的最短路徑長度。還設置一個矩陣path,path[i][j]是從Vi到Vj中間頂點序號不大于k的最短路徑上Vi的一個鄰接頂點的序號，約定Vi到Vj無路徑吋path[i][j]=0;由path[i][j]的值，可以得到從Vi到Vj最短路徑。實驗源碼：voidfloyd(inta[][n]，intcost[n][n],intpath[][n])//弗洛伊德算法{inti,j,k,next;for(i=0;i〈n;i++)for(j=

6、O;j

7、）//輸山{for（j=0;j%d無可達路徑",i+1,j+1）;//printfrrT）;}else{printf（〃％d〃，i+1）;while（q!=j+1）{printf（"—〉％d",q）;//printf（"%d〃，a[i+l][q]）;q=path[q-l][j];}printf（〃一>%d，z,j+1）;}三、結論1、實驗結果**

8、***輸出任意兩點間的最短距離和經過路徑如下*?01