迪杰斯特拉算法計(jì)算最短路徑

《迪杰斯特拉算法計(jì)算最短路徑》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

2、相關(guān)處理，將其從起點(diǎn)處“切斷”并展開為二維圖，然后根據(jù)此圖建立關(guān)聯(lián)矩陣。同時(shí)，我們考慮到最短路徑可能會(huì)與切斷線有交點(diǎn)，在切斷線以西找出若干地點(diǎn)一分為二，修改關(guān)聯(lián)矩陣。對(duì)于題目中缺失的兩處數(shù)據(jù)，本文將以當(dāng)時(shí)的交通數(shù)據(jù)為基礎(chǔ)，經(jīng)過合理的數(shù)據(jù)處理，結(jié)合GoogleEarth測(cè)距軟件與題目數(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)游時(shí)間和最短路徑，進(jìn)而判斷出所選擇的路徑是否能讓他贏得賭注。根據(jù)我們的求解

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

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

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

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

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

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