基于MATLAB求解最短路問題

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

2、1到v6應(yīng)選擇哪一路徑使你的費用最省。 1.2 分析問題 這屬于一個典型的求解最短路的問題，圖中頂點代表六個城市，邊上的權(quán)數(shù)表示該段公路的長度，題目所求為從v1到v6、的一條費用最省的路徑，我們假設(shè)所需費用僅與路徑長短有關(guān)，因此求費用最省的路徑即求權(quán)值最小的路徑。網(wǎng)絡(luò)圖中各權(quán)值均為正，可以使用Dijkstra算法。 1.3 數(shù)據(jù)整理 將網(wǎng)絡(luò)圖中各邊的權(quán)作如下整理以方便程序運行 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.數(shù)學(xué)原理 2.1 Dijkstra算法介紹Dijkstra 算法思想為：設(shè)G=（V，E）是一個帶權(quán)有向圖（也可以是無向圖，無向圖是有向圖的特例）， 把圖中頂點集合V分成兩組：第一組為已求出最短路徑的頂點集合（用S 表示，初始時S 中只有一個源點，以后每求得一條最短路徑，就將其加入到集合S 中，直到全部頂點都加入到S 中，算法就結(jié)束了）；第二組為其余未確定最短路徑的頂點集合（ 用U 表示）， 按最短路徑長度的遞增

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

5、 為新考慮的中間點，修改U 中各頂點的距離； 若從源點v 到頂點u的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u 的距離值，修改后的距離值的頂點k 的距離加上邊上的權(quán)。第四，重復(fù)步驟第二步和第三步直到所有頂點都包含在S 中。3. 程序設(shè)計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. 結(jié)果分析 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 運行結(jié)果 4.3 結(jié)果分析由運行結(jié)果可知，從V1到V6的最短路徑長度為10，路徑為：V1->V3->V2->V5->V6，結(jié)合網(wǎng)絡(luò)圖進行驗證，所求即為最短路。并且利用上述程序還可求得網(wǎng)絡(luò)中任意兩點之間的最短路徑。5. 學(xué)習(xí)體會 MATLAB是美國MathWorks公司出品的商業(yè)數(shù)學(xué)軟件，用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計

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

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

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