基于MATLAB求解最短路問題

1、基于MATLAB求解最短路問題1.引言 MATLAB和Mathematica、Maple并稱為三大數學軟件。它在數學類科技應用軟件中在數值計算方面首屈一指。通過本學期的學習了解和上機實踐，已經初步掌握使用MATLAB工具解決實際問題的能力。結合運籌學課程的學習，我考慮使用MATLAB求解最短路問題，而在所有求解最短路的方法中，Dijkstra算法是最為經典的一種，因此本文主要解決在MATLAB環(huán)境下使用Dijkstra算法求解最短路。1.1 提出問題設6個城市v1,v2,.,v6之間的一個公路網(圖1)每條公路為圖中的邊,邊上的權數表示該段公路的長度(單位:百公里),設你處在城市v1,那么從v

2、1到v6應選擇哪一路徑使你的費用最省。 1.2 分析問題 這屬于一個典型的求解最短路的問題，圖中頂點代表六個城市，邊上的權數表示該段公路的長度，題目所求為從v1到v6、的一條費用最省的路徑，我們假設所需費用僅與路徑長短有關，因此求費用最省的路徑即求權值最小的路徑。網絡圖中各權值均為正，可以使用Dijkstra算法。 1.3 數據整理 將網絡圖中各邊的權作如下整理以方便程序運行 W(1,2)=5; W(2,1)=5; W(1,3)=2; W(3,1)=2; W(2,3)=1; W(3,2)=1; W(2,4)=5; W(4,2)=5; W(2,5)=5; W(5,2)=5; W(3,4)=8;

3、W(4,3)=8; W(3,5)=10; W(5,3)=10; W(4,5)=2; W(5,4)=2; W(4,6)=5; W(6,4)=5; W(5,6)=2; W(6,5)=2;2.數學原理 2.1 Dijkstra算法介紹Dijkstra 算法思想為：設G=（V，E）是一個帶權有向圖（也可以是無向圖，無向圖是有向圖的特例）， 把圖中頂點集合V分成兩組：第一組為已求出最短路徑的頂點集合（用S 表示，初始時S 中只有一個源點，以后每求得一條最短路徑，就將其加入到集合S 中，直到全部頂點都加入到S 中，算法就結束了）；第二組為其余未確定最短路徑的頂點集合（ 用U 表示）， 按最短路徑長度的遞增

4、次序依次把第二組的頂點加入S 中。在加入的過程中，總保持從源點v 到S 中各頂點的最短路徑長度不大于從源點v 到U 中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S 中的頂點的距離就是從v 到此頂點的最短路徑長度，U中的頂點的距離，是從v 到此頂點只包括S 中的頂點為中間頂點的當前最短路徑長度。其步驟主要有：第一，初始時，S 只包含源點，即S頂點，v 的距離為0。U 包含除v 外的其他頂點，U 中頂點u 距離為邊上的權（若v 與u 有邊）或（若u 不是v 的出邊鄰接點）。第二，從U 中選取一個距離v 最小的頂點k，把k 加入S 中（該選定的距離就是v 到k 的最短路徑長度）。第三，以k

5、 為新考慮的中間點，修改U 中各頂點的距離； 若從源點v 到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u 的距離值，修改后的距離值的頂點k 的距離加上邊上的權。第四，重復步驟第二步和第三步直到所有頂點都包含在S 中。3. 程序設計function c0,c,path0,path=dijkstra(s,t,C,flag)s=floor(s);t=floor(t);n=size(C,1);label=ones(1,n)*inf;label(s)=0;S=s;Sbar=1:s-1,s+1:n;c0=0;path=zeros(n,n);path(:,1)=s;c=ones(1,

6、n)*inf;parent=zeros(1,n);i=1; % number of points in point set S.while i<n % for each point in Sbar, replace label(Sbar(j) by % min(label(Sbar(j),label(S(k)+C(S(k),Sbar(j) for j=1:n-i for k=1:i if label(Sbar(j) > label(S(k)+C(S(k),Sbar(j) label(Sbar(j)=label(S(k)+C(S(k),Sbar(j); parent(Sbar(j)=

7、S(k); end end end % Find the minmal label(j), j in Sbar. temp=label(Sbar(1); son=1; for j=2:n-i if label(Sbar(j)< temp temp=label(Sbar(j); son=j; end end % update the point set S and Sbar S=S,Sbar(son); Sbar=Sbar(1:son-1),Sbar(son+1:n-i); i=i+1; % if flag=1, just output the shortest path between

8、s and t. if flag=1 && S(i)=t son=t; temp_path=son; if son=s while parent(son)=s son=parent(son); temp_path=temp_path,son; end temp_path=temp_path,s; end temp_path=fliplr(temp_path); m=size(temp_path,2); path0(1:m)=temp_path; c_temp=0; for j=1:m-1 c_temp=c_temp+C(temp_path(j),temp_path(j+1);

9、end c0=c_temp; path(t,1:m)=path0; c(t)=c0; return endend% Form the output resultsfor i=1:n son=i; temp_path=son; if son=s while parent(son)=s son=parent(son); temp_path=temp_path,son; end temp_path=temp_path,s; end temp_path=fliplr(temp_path); m=size(temp_path,2); path(i,1:m)=temp_path; c_temp=0; fo

10、r j=1:m-1 c_temp=c_temp+C(temp_path(j),temp_path(j+1); end c(i)=c_temp; c0=c(t); path0=path(t,:);endreturn4. 結果分析 4.1 運行程序clcs=1;t=6;flag=1;W=ones(9,9)*inf; % for i=1:9 W(i,i)=0;endW(1,2)=5; W(2,1)=5;W(1,3)=2; W(3,1)=2;W(2,3)=1; W(3,2)=1;W(2,4)=5; W(4,2)=5;W(2,5)=5; W(5,2)=5;W(3,4)=8; W(4,3)=8;W(3,5

11、)=10; W(5,3)=10;W(4,5)=2; W(5,4)=2;W(4,6)=5; W(6,4)=5;W(5,6)=2; W(6,5)=2;c0,c,path0,path=dijkstra(s,t,W,flag);c0path0 4.2 運行結果 4.3 結果分析由運行結果可知，從V1到V6的最短路徑長度為10，路徑為：V1->V3->V2->V5->V6，結合網絡圖進行驗證，所求即為最短路。并且利用上述程序還可求得網絡中任意兩點之間的最短路徑。5. 學習體會 MATLAB是美國MathWorks公司出品的商業(yè)數學軟件，用于算法開發(fā)、數據可視化、數據分析以及數值計

12、算的高級技術計算語言和交互式環(huán)境，主要包括MATLAB和Simulink兩大部分。MATLAB是matrix&laboratory兩個詞的組合，意為矩陣工廠（矩陣實驗室）。是由美國mathworks公司發(fā)布的主要面對科學計算、可視化以及交互式程序設計的高科技計算環(huán)境。它將數值分析、矩陣計算、科學數據可視化以及非線性動態(tài)系統(tǒng)的建模和仿真等諸多強大功能集成在一個易于使用的視窗環(huán)境中，為科學研究、工程設計以及必須進行有效數值計算的眾多科學領域提供了一種全面的解決方案，并在很大程度上擺脫了傳統(tǒng)非交互式程序設計語言（如C、Fortran）的編輯模式，代表了當今國際科學計算軟件的先進水平。Matl

13、ab的學習是在運籌學之后開始的，雖然是作為選修課，也只安排了短短的10次課，但從一開始學習，我就抱著要掌握好這個工具的態(tài)度上課，因為不管是數學建模還是運籌學中，都可以用到它解決很多實際問題。課堂上教員給我們講解了軟件的基本操作并介紹了大量常用的命令，通過理論學習和上機實踐操作，慢慢的從開始的完全不懂漸漸能夠編寫一些簡單的M文件解決一些應用題，其中的成就感是相當令人欣慰的。雖然在此之前我們還學過C語言、C+和數據庫，也可以用它們來編程解題，但相比之下，使用MATLAB要簡單得多，同樣的一個問題，用編程的方法可能需要編寫很多條代碼，在這個軟件中卻可以輕松實現(xiàn)。“師傅領進門，修行靠個人”，受限于開課

14、課時，教員不可能給我們做太過深入的教學，因此要想學好這個軟件，最重要的還是靠自己課下的探索，任何工具性的東西都是這樣，只有練熟才了生巧。 對提高matlab編程能力的方法，我想主要有以下三個： 1、查help 在第一節(jié)課教員就向我們介紹了help命令，在學習過程中，時常遇到一些不知道的關鍵字，這時候只要通過help命令就可以找到該關鍵字的介紹，并且還有部分舉例，非常有助于理解程序。 2、多上論壇，搜索帖子、發(fā)帖詢問 網上有很多關于MATLAB的貼吧和論壇，許多學習這個程序的人都在這里交流，有初學者也有高手，上論壇的一個好處就是可以知道別人在學習過程中都遇到了一些什么問題，他們是怎么解決的，有什么好的學習經驗和方法可以供自己借鑒，甚至也可以自己發(fā)帖和別人交流，請教高手解答自己的困惑等等。 3、閱讀別人、特別是牛人的程序 多閱讀程序永遠是編程類軟件學