基于Dijkstra算法的環游世界最佳路徑選擇數學建模協會編號：69姓名1：李明宇姓名2：楊軍姓名3：艾建行指導教師：李學文評閱編號：評閱專家1評閱專家2評閱專家3評閱專家4評閱專家5摘要本文根據題中所給數據，通過建立基于Dijkstra算法的最短路徑模型，為著名的《80天環游世界》中福格的壯舉選取最優路徑，從而判斷出基于當時的交通環境不能實現該想法，同時解決了當起點發生改變時能否通過尋找最佳路徑，達到在一定時間內完成環游世界的目的。在具體求解過程中，我們將從倫敦環游世界的不同路線的交通網絡圖劃分成五個小區域，然后利用Dijkstra算法求取出各個區域的不同起點到各個終點的最短路徑，然后將五個區域組合，得到簡化后的環游世界的交通網絡圖，最后用同一算法得到從倫敦出發，環游世界的最短天數為81天，最佳路徑為：1倫敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork1倫敦，從而得出他不能贏得賭注的結論，同時，80天與81天相差不多，且注意到題中31-32﹑15-19之間所需天數未給出，若已知該時間且不長，則很有可能所需天數少于80天。運用類似方法計算出當環游世界的起點變為上海時，依據同一交通路線圖并且在交通環境沒有變化的前提下，得到環游世界的最短天數為77天，最短路徑為：37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai，從而得到此時他可以贏得賭注的結論。最后，我們對Diskstra算法進行了優化，從而提高了求最短路徑時的運行速度，增加了算法的執行效率。關鍵字：Dijkstra算法最優路徑分區簡化標號法一問題重述在儒勒·凡爾納的著名小說《環游世界80天》中，英國紳士福格在倫敦與人打賭能夠在80天內環游世界，這在當時的1872年是一個了不起的壯舉。當時最快的旅行方式是火車和輪船，然而世界上大部分地區還是靠馬車、大象、驢子或者步行來旅行。下面是一個從倫敦環游世界不同路線的交通網絡圖，福格選擇的是往東走，每段路線所需要的天數顯示在圖上，旅行的時間基于1872年能采用的旅行方式以及距離。請設計一個算法為福格選擇一條最佳路徑，即環游世界天數最短，你選擇的路徑能讓他贏得賭注嗎？如果他在別的地方與人打賭，比如紐約或者上海，結果會怎樣？交通網絡圖如下：二問題分析1.對問題一的分析：問題一要求通過設計一個算法選擇最佳路徑，并判斷福格是否能在八十天內環游世界。我們可以通過將題中所給的交通網絡路線圖分區域尋找最佳路徑，達到簡化的效果，最后得到合并后的簡化的交通路線圖，從而得到最短路徑以及此時所需的時間。2.對問題二的分析：問題二將環游世界的起點改變為上海或紐約，在此我隊對從上海出發繼續向東旅行的情況利用相似的方法進行求解，從而判斷出此時的最短路徑及所需最少的時間。三模型假設與符號說明(一)模型假設題中所給的交通網絡路線圖所提供的時間準確。福格在旅行中沒有發生意外情況導致旅行路線發生改變。起點改變時其他條件均不變。除出發點外，每個地點只到達一次。(二)符號說明由頂點V,弧A,和權值W組成的有向網絡PD中從到的一條路P中所有弧的權之和到自身的長度四模型建立與求解1問題一的分析與求解（1）模型的引入：取最短路徑問題給定有向網絡，任意弧，有權，給定D中的兩個頂點，。設P是D中從到的一條路，定義路P的權（長度）是P中所有弧的權之和，記為。最短路問題就是要在所有從到的路中，求一條路P0，使稱是從到的最短路。路P0的權稱為從到的路長,記為。Dijkstra算法思想：將中到所有其它頂點的最短路按其路長從小到大排列為：表示到自身的長度，相應最短路記為：一定只有一條弧，記取最小值的點為，。假定的值已求出，對應的最短路分別為：記則使上式達到最小值的點可取為。計算過程中可采用標號方法：中的點，值是到的最短路長度，相應的點記“永久”標號；中的點，值是到的最短路長度的上界，相應的點記“臨時”標號，供進一步計算使用。前點標號:表示點到的最短路上的前一點。如，表示vs到的最短路上前一點是。Dijkstra算法步驟：第1步：令,則令，,,，第2步：(選永久標號)在中選一點，滿足如果，停止，從到中各點沒有路；否則，轉第3步。第3步：（給點永久性標號）令如果，結束，到所有的點的最短路已經求得；否則，轉第4步。第4步：(修改臨時標號)對所有，如果，令否則,不變,把k換成k+1，返回第2步。（2）模型的求解：交通網絡圖如下：在這張地圖上所涉及的共有54個點，若再加上周期延拓，該數字將達到60，將這60個點之間的關系表現在矩陣中，不僅會造成輸入繁瑣﹑出錯可能性大、移植性差等問題，還由于矩陣所占空間與點的個數成二次曲線，點過多將大幅度提升計算機的負擔，延長運算時間，降低模型的效果。因此我們將這個地圖分為5個模塊，每個模塊中含有921個點不等，有效提高了建模的效率。這5個模塊分別如下所示：模塊1簡化后結果：上圖中，以倫敦為出發點，分別以18（St.Peterburg）、19（Moscow）、20（Kiev）、21（Istanbul）、17（Athens）為終點，得出了由起點到各終點的最短時間分別為9﹑13﹑13﹑10﹑11天。模塊2簡化后結果：模塊2以模塊1的終點：18（St.Peterburg）、19（Moscow）、20（Kiev）、21（Istanbul）、17（Athens）為起點，以27（Novosibirsk）、24（Tehran）、23（Aden）為終點，得出了各起點至終點的最短天數。圖中數字含義同模塊1.模塊3簡化后結果：模塊3以模塊2的終點：27（Novosibirsk）、24（Tehran）、23（Aden）為起點，以34（Beijing）、37（Shanghai）、35（HongKong）、33（Singapore）為終點，得出由各起點至終點的最短天數。模塊4簡化后結果：該模塊原理同前模塊，以34（Beijing）、37（Shanghai）、35（HongKong）、33（Singapore）為起點，以42（Seattle）、41（SanFrancisco）、43（LosAngeles）45（Panama）為終點。模塊5簡化后結果：以上為模塊5，以42（Seattle）、41（SanFrancisco）、43（LosAngeles）45（Panama）為起點，1（倫敦）、2（Lisbon）、3（Casablanca）為終點，本模塊中本不需要2（Lisbon）3（Casablanca），只需要終點倫敦即可，但考慮到模塊的完整性和后面模型的需要將其加入。經過以上模塊的分解，我們將一個很大的地圖化解為5個較小的圖，這5個模塊的起點與終點之間的所有點就可以忽略不計，只考慮起點與終點之間的天數即可，將一個54點的圖化為了1+5+3+4+4=17點的圖，再將這個17點圖帶入Dijkstra算法中求解即可得出最短天數的路徑為：1倫敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Senver50Chicago53NewYork1倫敦所需最短天數為：81天。80天與81天相差不多，且注意到題中31-32﹑15-19之間所需天數未給出，若已知該時間且不長，則很有可能所需天數少于80天。2模型二的求解：從上海繞行與從倫敦繞行思路相同，只是模塊稍有不同：模塊1：本模型中上海作為起點34（Beijing）35（HongKong）33（Singapore）本不需要，但考慮到模塊的完整性這里將其加入，圖中數字與前相同。模塊2：模塊3：模塊4：模塊5：利用Dijkstra算法中求解即可得出最短天數的路徑為：37Shanghai39Yokohma41SanFrancisco47Senver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cario23Aden28Bombay31Calutta33Singapore35HongKong37Shanghai最短天數為77天，得出他如果在上海出發，則可以贏得賭注。五模型優化由于經典Dijkstra算法在節點個數較多時會出現運行效率低，內存占用大，出錯率高，靈活性差等缺點，于是我們對經典Dijkstra算法進行了優化，對搜索網絡進行了分區域處理得到“優化Dijkstra算法”從模型的求解過程可以看出，若將該地圖分為幾個模塊，即使要換一個地點來計算最短時間也可以很快解決，直接套用原模塊即可，但是若將整個地圖全部輸入矩陣中，一旦更換地點，將不得不重新輸入圖矩陣，圖的規模越大，這樣所浪費的時間越多，出錯率越高，分塊的優點就充分體現了出來。優化Dijkstra算法與原始Dijkstra算法的搜索范圍比較示意圖如圖2．2所示。由圖2．2可見，原始Dijkstra算法的搜索過程(見圖2．2a)，是以源點為圓心的一系列同心圓，搜索過程沒有考慮終點所在的方向或位置，在從源點出發的搜索過程中，其他結點與終點被搜索到的概率是相同的。“優化Dijkstra算法”的搜索過程(見圖2．2b)是以源點和終點為焦點的一系列“同心橢圓”，永久標記點的選取原則為：當前結點距源點的最短距離與此結點到終點的直線距離之和最小者被選取為永久標記點。所以搜索過程趨向于終點，搜索過程到達終點的速度明顯快于原始Di]kstm算法，搜索到的結點也少于原始Dijkstra算法。六參考文獻[1]費培之圖和網絡及其應用四川大學出版社1996.8[2]李雷基于地圖分區算法求解動態最佳路徑的研究與實現江蘇大學碩士學位論文2004.6[3]楊長保，王開義，馬生密一種晟短路徑分析優化算法的實現吉林大學學報(信息科學版)．第20卷，第2期，2002年6月[4]柬濤，范東明OlS分析中最短路徑問題的圈論解決方法四川測繪，2002年04期七附錄function[S,D]=minRoute(i,m,W)%圖與網絡論中求最短路徑的Dijkstra算法M-函數%i為最短路徑的起始點,m為圖頂點數,W為圖的帶權鄰接矩陣，%不構成邊的兩頂點之間的權用inf表示。顯示結果為：S的每%一列從上到下記錄了從始點到終點的最短路徑所經頂點的序號；%D是一行向量，記錄了S中所示路徑的大小;dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];%dd的第二行是每次求出的最短路徑的終點，第一行是最短路徑的值kk=2;[mdd,ndd]=size(dd);while~isempty(V)[tmpd,j]=min(W(i,V));tmpj=V(j);fork=2:ndd[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));tmp2=V(jj);tt(k-1,:)=[tmp1,tmp2,jj];endtmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));iftmp3==tmpd,ss(1:2,kk)=[i;tmp(tmp4,2)];else,tmp5=find(ss(:,tmp4)~=