基于MATLAB求解短路問題

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

2、的長度 (單位: 百公里), 設(shè)你處在城市 v1, 那么 從 v1 到 v6應(yīng)選擇哪一路徑使你的費用最省。分析問題 這屬于一個典型的求解最短路的問題，圖中頂點代表六個城市，邊上 的權(quán)數(shù)表示該段公路的長度， 題目所求為從 v1到 v6、的一條費用最省的路徑， 我們假設(shè)所需費用僅與路徑長短有關(guān)，因此求費用最省的路徑即求權(quán)值最 小的路徑。網(wǎng)絡(luò)圖中各權(quán)值均為正，可以使用 Dijkstra 算法。數(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,

3、5)=5; W(5,2)=5; W(3,4)=8; 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;數(shù)學(xué)原理Dijkstra 算法介紹Dijkstra 算法思想為：設(shè) G=(V，E)是一個帶權(quán)有向圖(也可以是無 向圖，無向圖是有向圖的特例) ， 把圖中頂點集合 V 分成兩組：第一組為 已求出最短路徑的頂點集合(用 S 表示，初始時 S 中只有一個源點，以后 每求得一條最短路徑，就將其加入到集合 S 中，直到全部頂點都加入到 S 中，算法就結(jié)束了)；第二組為其余未確定最短

4、路徑的頂點集合( 用 U 表 示)， 按最短路徑長度的遞增次序依次把第二組的頂點加入 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 中

5、選取一個距離 v 最小的頂點 k，把k 加入S 中(該選定的 距離就是 v 到k 的最短路徑長度)。第三，以k 為新考慮的中間點， 修改U 中各頂點的距離； 若從源點 v 到 頂點 u的距離(經(jīng)過頂點 k)比原來距離(不經(jīng)過頂點 k)短，則修改頂點 u 的距離值，修改后的距離值的頂點 k 的距離加上邊上的權(quán)第四，重復(fù)步驟第二步和第三步直到所有頂點都包含在 S 中程序設(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;

6、S=s;Sbar=1:s-1,s+1:n;c0=0; path=zeros(n,n); path(:,1)=s; c=ones(1,n)*inf; parent=zeros(1,n); i=1; % number of points in point set S. while i label(S(k)+C(S(k),Sbar(j) label(Sbar(j)=label(S(k)+C(S(k),Sbar(j); parent(Sbar(j)=S(k);endendend% Find the minmal label(j), j in Sbar.temp=label(Sbar(1);son=1;

7、for j=2:n-iif label(Sbar(j)V3-V2-V5-V6，結(jié)合網(wǎng)絡(luò)圖進(jìn)行驗證，所求即為最短路。并且利用 上述程序還可求得網(wǎng)絡(luò)中任意兩點之間的最短路徑。學(xué)習(xí)體會MATLAB是美國 MathWorks公司出品的商業(yè)數(shù)學(xué)軟件，用于算法開發(fā)、 數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計算的高級技術(shù)計算語言和交互式環(huán)境， 主要包括 MATLAB和 Simulink 兩大部分。MATLAB是 matrix&laboratory 兩個詞的組合，意為矩陣工廠（矩陣實 驗室）。是由美國 mathworks 公司發(fā)布的主要面對科學(xué)計算、可視化以及交 互式程序設(shè)計的高科技計算環(huán)境。它將數(shù)值分析、矩陣計算、科

8、學(xué)數(shù)據(jù)可 視化以及非線性動態(tài)系統(tǒng)的建模和仿真等諸多強(qiáng)大功能集成在一個易于使 用的視窗環(huán)境中，為科學(xué)研究、工程設(shè)計以及必須進(jìn)行有效數(shù)值計算的眾 多科學(xué)領(lǐng)域提供了一種全面的解決方案，并在很大程度上擺脫了傳統(tǒng)非交 互式程序設(shè)計語言（如 C、Fortran ）的編輯模式，代表了當(dāng)今國際科學(xué)計 算軟件的先進(jìn)水平。Matlab 的學(xué)習(xí)是在運籌學(xué)之后開始的，雖然是作為選修課，也只安排 了短短的 10 次課，但從一開始學(xué)習(xí)，我就抱著要掌握好這個工具的態(tài)度上 課，因為不管是數(shù)學(xué)建模還是運籌學(xué)中，都可以用到它解決很多實際問題。 課堂上教員給我們講解了軟件的基本操作并介紹了大量常用的命令，通過 理論學(xué)習(xí)和上機(jī)實踐操

9、作，慢慢的從開始的完全不懂漸漸能夠編寫一些簡 單的 M 文件解決一些應(yīng)用題，其中的成就感是相當(dāng)令人欣慰的。雖然在此 之前我們還學(xué)過 C語言、 C+和數(shù)據(jù)庫，也可以用它們來編程解題，但相比 之下，使用 MATLAB要簡單得多，同樣的一個問題，用編程的方法可能需要 編寫很多條代碼，在這個軟件中卻可以輕松實現(xiàn)?！皫煾殿I(lǐng)進(jìn)門，修行靠個人” ，受限于開課課時，教員不可能給我們做 太過深入的教學(xué)，因此要想學(xué)好這個軟件，最重要的還是靠自己課下的探 索，任何工具性的東西都是這樣，只有練熟才了生巧。對提高 matlab 編程能力的方法，我想主要有以下三個：、查 help在第一節(jié)課教員就向我們介紹了 help 命

10、令，在學(xué)習(xí)過程中，時常遇到 一些不知道的關(guān)鍵字，這時候只要通過 help 命令就可以找到該關(guān)鍵字的介 紹，并且還有部分舉例，非常有助于理解程序。、多上論壇，搜索帖子、發(fā)帖詢問網(wǎng)上有很多關(guān)于 MATLAB的貼吧和論壇，許多學(xué)習(xí)這個程序的人都在這里交流，有初學(xué)者也有高手，上論壇的一個好處就是可以知道別人在學(xué)習(xí) 過程中都遇到了一些什么問題，他們是怎么解決的，有什么好的學(xué)習(xí)經(jīng)驗 和方法可以供自己借鑒，甚至也可以自己發(fā)帖和別人交流，請教高手解答 自己的困惑等等。、閱讀別人、特別是牛人的程序 多閱讀程序永遠(yuǎn)是編程類軟件學(xué)習(xí)的必經(jīng)途徑，只有通過多閱讀，才 能理解算法的思想，熟悉代碼的編寫方法。當(dāng)然了，正如所有的程序語言 一樣，“3分課本 7分上機(jī)”，一定要動手才行， 不