迪杰斯特拉算法計算最短路徑

《迪杰斯特拉算法計算最短路徑》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

1、利用Dijkstra算法計算最短路徑摘要福格環(huán)游地球問題是一個十分典型的最短路徑求解問題，題設給出了當時世界上主要交通網(wǎng)絡圖及交通通暢的城市之間來往所需時長，并限定了福格的出行方向（福格選擇的是往東走），給出起止地點后要求找出福格環(huán)游世界天數(shù)最短的最佳路徑。我們認為，這個問題的實質在于最短路徑的求解和優(yōu)化。我們對比圖論中的多種最短路徑算法，決定利用Dijkstra算法解決這個問題。由于Dijkstra算法要求輸入圖G的關聯(lián)矩陣，且圖G為二維賦權圖，而題中給出的地圖可看成是三維環(huán)狀地圖，因此，我們對題設地圖做

2、相關處理，將其從起點處“切斷”并展開為二維圖，然后根據(jù)此圖建立關聯(lián)矩陣。同時，我們考慮到最短路徑可能會與切斷線有交點，在切斷線以西找出若干地點一分為二，修改關聯(lián)矩陣。對于題目中缺失的兩處數(shù)據(jù)，本文將以當時的交通數(shù)據(jù)為基礎，經(jīng)過合理的數(shù)據(jù)處理，結合GoogleEarth測距軟件與題目數(shù)據(jù)的合理類比，補充缺失數(shù)據(jù)，完成關聯(lián)矩陣。得到關聯(lián)矩陣后，我們分別以倫敦、紐約和上海作為起點，調整關聯(lián)矩陣起點和終點，用matlab編程進行求解得到最短環(huán)游時間和最短路徑，進而判斷出所選擇的路徑是否能讓他贏得賭注。根據(jù)我們的求解

3、結果，在這三個城市，福格均能在80天內環(huán)游地球，贏得賭注。本文進一步對此種算法的優(yōu)缺點、靈敏度與推廣性進行了分析，同時初步提出了兩種優(yōu)化方法。關鍵詞：最短路徑算法dijkstra算法算法優(yōu)化一、問題重述儒勒?凡爾納的著名小說《環(huán)游世界80天》中，英國紳士福格在倫敦與人打賭能夠在80天內環(huán)游世界，這在當時的1872年是一個了不起的壯舉。當時最快的旅行方式是火車和輪船，然而世界上大部分地區(qū)還是靠馬車、大象、驢子或者步行來旅行。下面是一個從倫敦環(huán)游世界不同路線的交通網(wǎng)絡圖，福格選擇的是往東走，每段路線所需要的天數(shù)

4、顯示在圖上（見附錄一），旅行的時間基于1872年能采用的旅行方式以及距離。我們將解決以下問題：1．我們將設計一個算法為福格選擇一條最佳路徑，即環(huán)游世界天數(shù)最短，并判斷所選擇的路徑是否能讓他贏得賭注。2．若他在別的地方與人打賭，如紐約或者上海，我們將分別設計最佳路徑并判斷所選擇的路徑是否能讓他贏得賭注。二、問題分析福格環(huán)游地球問題是一個十分典型的最短路徑求解問題，題設給出了當時世界上主要交通網(wǎng)絡圖及交通通暢的城市之間來往所需時長，并限定了福格的出行方向（福格選擇的是往東走），給出起止地點后要求找出福格環(huán)游世界

5、天數(shù)最短的最佳路徑。本題實質在于最短路徑的求解和優(yōu)化，如何求解最短路徑呢，我們聯(lián)系到圖論中求解最短路徑的Dijkstra算法，然而，要滿足Dijkstra算法的條件，首要任務是弄清如何處理題設所給的世界交通網(wǎng)絡圖。我們可以把題中給出的地圖看成是三維環(huán)狀地圖，而Dijkstra算法要求輸入圖G的關聯(lián)矩陣，且圖G為二維賦權圖，因此，我們應該對題設地圖做相關處理，將其從起點處“切斷”并展開為二維圖，然后根據(jù)此圖建立關聯(lián)矩陣。但是，考慮到最短路徑可能會與切斷線有交點，我們必須在切斷線以西找出若干地點一分為二，修改關

6、聯(lián)矩陣。在創(chuàng)建關聯(lián)矩陣的時候，必須考慮到如何估計兩處缺失的數(shù)據(jù)，當時的地區(qū)交通狀況文獻已經(jīng)無法查詢，因此，我們只能根據(jù)當?shù)刂車嗨频匦蔚貏萏幍囊阎煌顩r進行估值。如何估值呢，我們用GoogleEarth對兩地距離進行測量，并進行若干假設，與附近相似地形已知數(shù)據(jù)處進行同比例估值，得到近似結果。對于題目提出的問題，分別以倫敦、紐約和上海作為起點，我們只需調整關聯(lián)矩陣起點和終點用matlab編程進行求解即可得到最短環(huán)游時間和最短路徑，從而判斷出所選擇的路徑是否能讓他贏得賭注。三、基本假設1、題目中給出的數(shù)據(jù)均準

7、確。2、題目中給出的數(shù)據(jù)均采用當時能達到的最高效的交通方式。3、在環(huán)游地球的路程中，福格不會在任何地點因任何原因停留。4、相似地理環(huán)境下，兩地之間所需時間正比于兩地距離。5、GoogleEarth所測得的數(shù)據(jù)均準確。6、相近地理環(huán)境下兩地點間交通路線距離與直線距離近似成正比。7、1870年至今數(shù)據(jù)缺失處地形地勢未發(fā)生明顯變動。8、在旅行路途中因改變交通工具導致的可能的時間延誤已計入數(shù)據(jù)所給時間。9、在環(huán)球旅程中所有交通工具均能正常行駛。四、符號說明具體的符號使用將在具體使用處說明。五、模型的建立與求解5.1

8、缺失數(shù)據(jù)確定題目所給數(shù)據(jù)中有兩段路程具體數(shù)據(jù)缺失，需要自行估算。由于年代久遠，當時的確切數(shù)據(jù)已很難查出，我們決定利用googleearth軟件對路徑長度進行測距，結合當時的地理環(huán)境與題目已給出的數(shù)據(jù)進行估算。為了保證結果的合理性，對所有需要四舍五入的時間長度均采取進位的方式，由此計算的總天數(shù)不會超過實際所需天數(shù)，得到的數(shù)據(jù)相對合理。5.1.115Minsk~19MoscowMinsk作為在19世紀飛速發(fā)展的工業(yè)城