基于MATLAB求解短路問題

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

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

4、路徑的頂點(diǎn)集合( 用 U 表 示)， 按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入 S 中。在加入 的過程中，總保持從源點(diǎn) v 到 S 中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn) v 到 U 中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離， S 中的 頂點(diǎn)的距離就是從 v 到此頂點(diǎn)的最短路徑長(zhǎng)度， U中的頂點(diǎn)的距離， 是從 v 到此頂點(diǎn)只包括 S 中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。其步驟主要 有：第一，初始時(shí)， S 只包含源點(diǎn)，即 S頂點(diǎn)，v 的距離為0。U 包含 除v 外的其他頂點(diǎn)， U 中頂點(diǎn) u 距離為邊上的權(quán)(若 v 與u 有邊)或(若 u 不是 v 的出邊鄰接點(diǎn))。第二，從U 中

5、選取一個(gè)距離 v 最小的頂點(diǎn) k，把k 加入S 中(該選定的 距離就是 v 到k 的最短路徑長(zhǎng)度)。第三，以k 為新考慮的中間點(diǎn)， 修改U 中各頂點(diǎn)的距離； 若從源點(diǎn) v 到 頂點(diǎn) u的距離(經(jīng)過頂點(diǎn) k)比原來距離(不經(jīng)過頂點(diǎn) k)短，則修改頂點(diǎn) u 的距離值，修改后的距離值的頂點(diǎn) k 的距離加上邊上的權(quán)第四，重復(fù)步驟第二步和第三步直到所有頂點(diǎn)都包含在 S 中程序設(shè)計(jì) 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)行驗(yàn)證，所求即為最短路。并且利用 上述程序還可求得網(wǎng)絡(luò)中任意兩點(diǎn)之間的最短路徑。學(xué)習(xí)體會(huì)MATLAB是美國 MathWorks公司出品的商業(yè)數(shù)學(xué)軟件，用于算法開發(fā)、 數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算的高級(jí)技術(shù)計(jì)算語言和交互式環(huán)境， 主要包括 MATLAB和 Simulink 兩大部分。MATLAB是 matrix&laboratory 兩個(gè)詞的組合，意為矩陣工廠（矩陣實(shí) 驗(yàn)室）。是由美國 mathworks 公司發(fā)布的主要面對(duì)科學(xué)計(jì)算、可視化以及交 互式程序設(shè)計(jì)的高科技計(jì)算環(huán)境。它將數(shù)值分析、矩陣計(jì)算、科

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

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

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