最短路徑問題的算法分析及建模案例

1、最短路徑問題的算法分析及建模案例.摘要2.網(wǎng)絡(luò)最短路徑問題的基礎(chǔ)知識3有向圖5連通性錯誤！未定義書簽。割集錯誤！未定義書簽。最短路問題6.最短路徑的算法研究 錯誤！未定義書簽。最短路問題的提出6Bellman 最短路方程 錯誤！未定義書簽。Bellman-Ford算法的基本思想 錯誤！未定義書簽。Bellman-Ford 算法的步驟 錯誤!未定義書簽。實例錯誤！未定義書簽。Bellman-FORD算法的建模應(yīng)用舉例錯誤！未定義書簽。 TOC o 1-5 h z Dijkstra算法的基本思想6Dijkstra算法的理論依據(jù)6Dijkstra算法的計算步驟6Dijstre算法的建模應(yīng)用舉例 7兩

2、種算法的分析 錯誤!未定義書簽。.Diklstra 算法和Bellman-Ford算法思想有很大的區(qū)別錯誤！未定義書簽。Bellman-Ford 算法在求解過程中，每次循環(huán)都要修改所有頂點的權(quán)值，也就是說源點到各頂點最短路徑長度一直要到Bellman-Ford 算法結(jié)束才確定下來。錯誤!未定義書簽。.Diklstra 算法和Bellman-Ford算法的限制錯誤!未定義書簽。.Bellman-Ford 算法的另外一種理解錯誤!未定義書簽。.Bellman-Ford 算法的改進錯誤！未定義書簽。摘要近年來計算機發(fā)展迅猛，圖論的研究也得到了很大程度的發(fā)展，而最短路徑問題一直是圖論中的一個典型問題，

3、它已應(yīng)用在地理信息科學(xué)，計算機科學(xué)等諸多 領(lǐng)域。而在交通路網(wǎng)中兩個城市之間的最短行車路線就是最短路徑問題的一個典 型例子。由于最短路徑問題在各方面廣泛應(yīng)用，以及研究人員對最短路徑的深入研究， 使得在最短路徑問題中也產(chǎn)生了很多經(jīng)典的算法。在本課題中我將提出一些最短路徑問題的算法以及各算法之間的比較，最后將這些算法再應(yīng)用于實際問題的建 模問題中。關(guān)鍵詞：計算機 圖論交通道路網(wǎng)最短路徑A. In this paper,Computer developing rapidly in recent years, graph theory research also have been greatly de

4、veloped, and the shortest path problem is a typical problem in graph theory, it has been applied in geographical information science, computer science, and many other fields. And in the transportation network of the shortest route between two cities in is a typical example of the shortest path probl

5、em.Due to the shortest path problem is widely used in various aspects, and the researchers on the in-depth study of the shortest path, make in the shortest path problem also generates a lot of classical algorithm. In this topic Ill suggest some algorithm and the algorithm of the shortest path proble

6、m between the comparison, finally the algorithm is applied to the modeling of the actual problem again.Key words: computer graph traffic road network The shortest path前言最短路徑問題是圖論以及運籌學(xué)中的一個非常重要的問題，在生產(chǎn)實踐，運輸及工程建筑等方面有著十分廣泛的應(yīng)用。本文對圖論中的最短路徑問題進行分析， 對其運算解法進行分析尋求比較快捷的模型解法；主要解決的是從某個頂點到其 余各個頂點的最短路徑問題。本文從 Floyd算法

7、以及Dijkstra 算法兩種算法入 手，概述了這兩種方法的原理，提出了求解最短路徑問題的算法思想， 并且對兩 種算法進行分析比較，提出改進的方法。網(wǎng)絡(luò)最短路徑問題的基礎(chǔ)知識圖1圖圖G是一個（無向）圖，其中有序二元組（V,E） , V=vi, v2,. vn是頂點集，E= 0 是集，0是一個無序二元組 Vi , Vj 它表示該邊連接的是頂點Vi ,Vj。圖1就是一個圖注釋：圖形的大小，位置，形狀是無關(guān)緊要的。若q = Vi, Vj則稱eij連接Vi和Vj ;點m和Vj稱為0的頂點，Vi和Vj是鄰接的頂點；如果兩條邊有公共的一個頂點，則稱這兩邊是鄰接的。無環(huán)圖定義：沒有環(huán)的圖稱之為無環(huán)圖。簡單圖

8、定義：沒有環(huán)且沒有重邊的圖稱之為簡單圖。設(shè)6= (V,E)是一個簡單圖，則有|E|不大于|V| (|V|-1 ) /2完全圖定義：若上式的等號成立那么該圖中每對頂點恰好有一條邊相連，則稱該圖為完全圖。有向圖 定義：一個有向圖G是一個有序二元組(V,A) , V=vV2, ., vn是頂點集，A= a。稱為G的弧集，aij為有序二元組稱a。為m連向Vj的弧，a。為m的出弧，Vj的入弧；Vi稱為a。的得尾，V。稱為aj個有向圖。個有向圖。環(huán)定義：頭尾重合的弧稱為環(huán)。簡單有向圖定義：沒有環(huán)和重弧的有向圖稱為簡單有向圖。完全有向圖定義：設(shè)G= (V,E)是一個簡單有向圖，則|A|不大于|V| (|V|

9、-1 ),若等號成 立則稱這樣的圖為完全有向圖。途徑，跡，路定義:設(shè)圖G= (V,E),若它的某些頂點與邊可以排成一個非空的有限交錯序列定義:(Vo, 8, V1,. ek, Vk)，這里該途徑中邊互不相同，則稱為跡；如果頂點互不相同，則稱之為路。顯然路必為跡，但反之不一定成立。連通圖 定義：圖G中如果存在一條從頂點w到Vj的途徑，則稱m和Vj是連通的。如果圖G中任何兩個頂點都是連通的，則稱 G是連通圖。有向途徑定義：設(shè)有一個有向圖G= (V,A) , G中某些頂點與弧組成的非空有限序列(Vo , ai , vi , a2 , . , ak , vk)這里v0, . , vk V, a A,且

10、alVr, Vj),則稱它為從v0到vk的有向途 徑。類似的可定義有向跡，有向路，有向閉途徑，有向閉跡，有向回路(圈)等。 當(dāng)G時簡單有向圖時，從vo到vk的一條有向途徑可簡記為(vo, .,vk)。二最短路問題定義：所謂最短路徑是指如果從圖中某一頂點(稱為源點)到達另一頂點(稱為 終點)的路徑可能不止一條，如何找到一跳有向路徑使得沿這條路徑上各弧的權(quán) 值總和最小。2.1最短路問題的提出某旅客要從杭州乘飛機前往奧地利的薩爾斯堡，因為他害怕乘坐飛機，因此要選擇一條航線，使得在空中飛行的時間盡可能的少。如何選擇航線以達到要求。 為此構(gòu)造一個無向網(wǎng)絡(luò)總可以化成有向網(wǎng)絡(luò)。設(shè)G= (V,A,w)是一個有

11、向網(wǎng)絡(luò)，p為G中一條有向路，稱w (P) = w(a)為路 a P徑p的路長?，F(xiàn)找網(wǎng)絡(luò)中一條從指定頂點 vi到另一個指定頂點vj的最短有向路 徑。三最短路徑算法研究Dijkstra 算法Dijkstra算法的基本思想對網(wǎng)絡(luò)中每個頂點賦一個標(biāo)號，用來記錄從丫1頂點到該頂點的最短路的長度(稱 為永久標(biāo)號)或最短長度的上界(稱為臨時標(biāo)號)。算法開始時，只有頂點必被賦予永久標(biāo)號=0,其他頂點vi賦予臨時標(biāo)號Uj wj。一般的，算法在被臨時標(biāo) 號的頂點中尋找一個頂點vk,其臨時標(biāo)號uk最小，然后將vk賦予永久標(biāo)號uk, 并且對其余臨時標(biāo)號的頂點vj按照方式Uj minUj,uk wkj修正其標(biāo)號。算法在

12、 所有頂點被賦予永久標(biāo)號時結(jié)束。Dijkstra算法的理論依據(jù)(1)對于S中任意一頂點，其永久標(biāo)號都是從頂點M到該頂點的最短路的長度。(2)對于R中任意一頂點，其臨時標(biāo)號都是從頂點 %出發(fā)，只經(jīng)過S中頂點到達該頂點的最短路的長度。3.13 Dijkstra算法的計算步驟最短路徑問題是指在一個賦予權(quán)值的圖的兩個指定節(jié)點u0和v之間找出一條具有最小權(quán)值的路。Dijkstra 算法是一個解最短路徑問題的算法，這個算法不僅 可以找到最短的(uo, v),路徑而且可以給出從Uo到圖中所有節(jié)點的最短路徑， 基本步驟如下：(1)設(shè)D(Uo)=O,對所有節(jié)點w Uo來說，設(shè)D(w)=，并且將u0標(biāo)號為0, u

13、0-t, d為u0和w之間的權(quán)值(距離)。(2)按照每個沒有標(biāo)號的節(jié)點 w計算D(w), D(w) min D(w),D(t) L(t,w),L(t,w)表示節(jié)點t到節(jié)點w之間的權(quán)值。如果D(w)標(biāo)號被修改了說明在當(dāng)前得到的u0到w的最優(yōu)路徑上t和w相鄰，用tw記錄下來在所有D(w)中選擇一個最小的D(s)即D(s) minD(w) , w未標(biāo)號。將s標(biāo)號為D(s)/tw,表示節(jié)點u0到 s的最優(yōu)路徑的長度D(s)且tw與s相鄰。(3)如果重點v已經(jīng)標(biāo)號，則停止。得到一條從u0到v的最優(yōu)路徑。否則s-t, 反向。(4)按照上述步驟繼續(xù)計算。3.14 Dijstre算法的建模應(yīng)用舉例某城市要在該

14、城市所轄的 8個區(qū)中的5區(qū)建立一個取水點，如圖所示的是這8個區(qū)之間的分布以及相鄰各區(qū)的距離。 現(xiàn)要從Ui區(qū)向其他各區(qū)運水，求出Ui區(qū)到 其他各區(qū)的最短路徑。11先寫出帶權(quán)鄰接矩陣:0 2 1806 19W=1 2W=390 4 60 30因為G是無向圖，所以W是對稱矩陣。迭代次 數(shù)L(uJU1U2U3U4U5U6U7U81020218328104831058610126710127912812最后標(biāo) 記L (v)021736912Z (v)UiUiUiU6U2U5U4U5因止匕得至1最短路徑為：迭代次 數(shù)L(uJUiU2U3U4U5U6U7U8最后標(biāo) 記L (v)02i7369i2Z (v)U

15、iUiUiU6U2U5U4U5由上表可得到U1到各點的最短路徑為:UiU2 ；UiU3 ;Ui UUi U4 , UiU2 U4, UiU3 U4;UiU2U5 ;UiU2U5 U6 ；Ui Ui U4 U7 , UiU3U7 , UiU2 U5 U6U7 ；Ui Ui U2 U5 U8, UiU2U5U6U8。上述 Dijkstra 算法的 MATLAB:w=0 2 i 8 inf inf inf;2 0 inf 6 i inf inf inf ;i inf 0 7 inf inf 9 inf;8 6 7 0 5 i 2 inf;inf i inf 5 0 3 inf 9;inf inf i

16、nf i 3 0 4 6;inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0 n=size(w,i);wi=w(i,:);% 賦初值 %for i=i:nl(i)=wi(i);z(i)=i;ends=;s(i)=i;U=s(i);k=i;while kl(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u;endend endend l,z %求v* L1=1; for i=1:n for j=1:k if i=s(j) l1(i)=l1(i); elsel1(i)=inf;endend end lv=inf; for i=1:n if

17、 l1(i)lv lv=l1(i); v=i;end end lv,v s(k+1)=v k=k+1 u=s(k) end l,zFLOYD 算法FLOYD算法的基本思想直接在圖的帶權(quán)鄰接矩陣中使用插入頂點的方法依次構(gòu)造出n個矩陣D，D，D，使得最終得到的矩陣D成為圖的距離矩陣，并且同時求出插入的點的矩陣以便于得到兩點間的最短路徑。FLOYD算法原理(D floyDT法求路徑矩陣的方法：在建立距離矩陣的同時可建立路徑矩陣 R。(0)(0).R (rij ) v v, rijJ每一次求到一個D(k)時，按照下列的方式產(chǎn)生相應(yīng)的新R(k),(k) r (k) r ijk若d：(k 1),(k 1)

18、 dik否則,(k 1) dkj即當(dāng)Vk被插入在任何兩點間的最短路徑時，被記錄在R(k)中，依次求R時求得D，可由R來查找任何兩個點之間的最短路徑。FLOYDT法查找最短路徑的方法：如果rj(n)P ,那么點Pi是點i到點j的最短路的中點。用同樣的方法再查找，如果：(1)向點i查找得：韜P2, %) P3,., ip/Pk。(2)向點 j 查找得：rp1j(n) q,1 q2, . , j。那么從點i到j(luò)的最短路徑為：i,pk,., p2 , p1 ,q1,q2, . ,qm ,ji PkP3P2Pl fll A2 qin JFLOYD算法的算法步驟Floud算法算法目的：求任意兩個頂點間的最

19、短路徑。D(i, j)：表示i到j(luò)之間的距離。R(i, j):表示i到j(luò)之間的插入點。起始：選定帶權(quán)值的鄰接矩陣 w(i,j)(1)賦化 對所有的 i , j , d(i, j)w(i, j) , r(i, j) j , k 1。(2)更新 d(i,j), r(i,j)對所有的 i , j ,如果 d(i,k) d(k, j) d(i,d),那么 d(i, j) d(i,k) d(k, j) , r(i,j) k。(3)如果k=v,那么算法終止；否則k k 1,再次回到(2),以此類推FLOYD建模應(yīng)用舉例某個城市要建立一個消防站，為該城市所屬的七個區(qū)服務(wù)，如圖所示。問應(yīng)該把 這個消防站設(shè)置在

20、哪個區(qū)，才能使該消防站到最遠的區(qū)的路徑最短。用Floyd算法求出各點之間的距離，得到表格:ViV2V3V4V5V6V7Vi0351075.57V2302742.54V3520524.56V410750378.5V57423045.5V65.52.54.57401.5V77468.55.51.50從上表可以得出距離矩陣D d(j)7 730252010757423025201075742 TOC o 1-5 h z 742.54524.560378.53045.55.5 2.5 4.5 745.5 2.5 4.5 740 1.5468.5 5.5 1.5 0計算在各點Vi設(shè)立服務(wù)設(shè)施的最大服務(wù)距離S(vi),鼠,)maxdj, i,j 1,2,3.,7。1 j v JS(vi) 10, S(V2