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

《迪杰斯特拉算法計算最短路徑》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

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

4、將解決以下問題：1．我們將設(shè)計一個算法為福格選擇一條最佳路徑，即環(huán)游世界天數(shù)最短，并判斷所選擇的路徑是否能讓他贏得賭注。2．若他在別的地方與人打賭，如紐約或者上海，我們將分別設(shè)計最佳路徑并判斷所選擇的路徑是否能讓他贏得賭注。二、問題分析福格環(huán)游地球問題是一個十分典型的最短路徑求解問題，題設(shè)給出了當(dāng)時世界上主要交通網(wǎng)絡(luò)圖及交通通暢的城市之間來往所需時長，并限定了福格的出行方向（福格選擇的是往東走），給出起止地點(diǎn)后要求找出福格環(huán)游世界天數(shù)最短的最佳路徑。本題實質(zhì)在于最短路徑的求解和優(yōu)化，如何求解最短路徑呢，我們聯(lián)系到圖論中求解最短路徑的

5、Dijkstra算法，然而，要滿足Dijkstra算法的條件，首要任務(wù)是弄清如何處理題設(shè)所給的世界交通網(wǎng)絡(luò)圖。我們可以把題中給出的地圖看成是三維環(huán)狀地圖，而Dijkstra算法要求輸入圖G的關(guān)聯(lián)矩陣，且圖G為二維賦權(quán)圖，因此，我們應(yīng)該對題設(shè)地圖做相關(guān)處理，將其從起點(diǎn)處“切斷”并展開為二維圖，然后根據(jù)此圖建立關(guān)聯(lián)矩陣。但是，考慮到最短路徑可能會與切斷線有交點(diǎn)，我們必須在切斷線以西找出若干地點(diǎn)一分為二，修改關(guān)聯(lián)矩陣。在創(chuàng)建關(guān)聯(lián)矩陣的時候，必須考慮到如何估計兩處缺失的數(shù)據(jù)，當(dāng)時的地區(qū)交通狀況文獻(xiàn)已經(jīng)無法查詢，因此，我們只能根據(jù)當(dāng)?shù)刂車嗨?/p>

6、地形地勢處的已知交通狀況進(jìn)行估值。如何估值呢，我們用GoogleEarth對兩地距離進(jìn)行測量，并進(jìn)行若干假設(shè)，與附近相似地形已知數(shù)據(jù)處進(jìn)行同比例估值，得到近似結(jié)果。對于題目提出的問題，分別以倫敦、紐約和上海作為起點(diǎn)，我們只需調(diào)整關(guān)聯(lián)矩陣起點(diǎn)和終點(diǎn)用matlab編程進(jìn)行求解即可得到最短環(huán)游時間和最短路徑，從而判斷出所選擇的路徑是否能讓他贏得賭注。三、基本假設(shè)1、題目中給出的數(shù)據(jù)均準(zhǔn)確。2、題目中給出的數(shù)據(jù)均采用當(dāng)時能達(dá)到的最高效的交通方式。3、在環(huán)游地球的路程中，福格不會在任何地點(diǎn)因任何原因停留。4、相似地理環(huán)境下，兩地之間所需時間正

7、比于兩地距離。5、GoogleEarth所測得的數(shù)據(jù)均準(zhǔn)確。6、相近地理環(huán)境下兩地點(diǎn)間交通路線距離與直線距離近似成正比。7、1870年至今數(shù)據(jù)缺失處地形地勢未發(fā)生明顯變動。8、在旅行路途中因改變交通工具導(dǎo)致的可能的時間延誤已計入數(shù)據(jù)所給時間。9、在環(huán)球旅程中所有交通工具均能正常行駛。四、符號說明具體的符號使用將在具體使用處說明。五、模型的建立與求解5.1缺失數(shù)據(jù)確定題目所給數(shù)據(jù)中有兩段路程具體數(shù)據(jù)缺失，需要自行估算。由于年代久遠(yuǎn)，當(dāng)時的確切數(shù)據(jù)已很難查出，我們決定利用googleearth軟件對路徑長度進(jìn)行測距，結(jié)合當(dāng)時的地理環(huán)境與

8、題目已給出的數(shù)據(jù)進(jìn)行估算。為了保證結(jié)果的合理性，對所有需要四舍五入的時間長度均采取進(jìn)位的方式，由此計算的總天數(shù)不會超過實際所需天數(shù)，得到的數(shù)據(jù)相對合理。5.1.115Minsk~19MoscowMinsk作為在19世紀(jì)飛速發(fā)展的工業(yè)城