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

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

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

3、它已應(yīng)用在地理信息科學(xué)，計(jì)算機(jī)科學(xué)等諸多 領(lǐng)域。而在交通路網(wǎng)中兩個(gè)城市之間的最短行車路線就是最短路徑問題的一個(gè)典 型例子。由于最短路徑問題在各方面廣泛應(yīng)用，以及研究人員對最短路徑的深入研究， 使得在最短路徑問題中也產(chǎn)生了很多經(jīng)典的算法。在本課題中我將提出一些最短路徑問題的算法以及各算法之間的比較，最后將這些算法再應(yīng)用于實(shí)際問題的建 模問題中。關(guān)鍵詞：計(jì)算機(jī) 圖論交通道路網(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前言最短路徑問題是圖論以及運(yùn)籌學(xué)中的一個(gè)非常重要的問題，在生產(chǎn)實(shí)踐，運(yùn)輸及工程建筑等方面有著十分廣泛的應(yīng)用。本文對圖論中的最短路徑問題進(jìn)行分析， 對其運(yùn)算解法進(jìn)行分析尋求比較快捷的模型解法；主要解決的是從某個(gè)頂點(diǎn)到其 余各個(gè)頂點(diǎn)的最短路徑問題。本文從 Floyd算法

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

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

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

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

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

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

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

14、城市所轄的 8個(gè)區(qū)中的5區(qū)建立一個(gè)取水點(diǎn)，如圖所示的是這8個(gè)區(qū)之間的分布以及相鄰各區(qū)的距離。 現(xiàn)要從Ui區(qū)向其他各區(qū)運(yùn)水，求出Ui區(qū)到 其他各區(qū)的最短路徑。11先寫出帶權(quán)鄰接矩陣:0 2 1806 19W=1 2W=390 4 60 30因?yàn)镚是無向圖，所以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到各點(diǎn)的最短路徑為: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)鄰接矩陣中使用插入頂點(diǎn)的方法依次構(gòu)造出n個(gè)矩陣D，D，D，使得最終得到的矩陣D成為圖的距離矩陣，并且同時(shí)求出插入的點(diǎn)的矩陣以便于得到兩點(diǎn)間的最短路徑。FLOYD算法原理(D floyDT法求路徑矩陣的方法：在建立距離矩陣的同時(shí)可建立路徑矩陣 R。(0)(0).R (rij ) v v, rijJ每一次求到一個(gè)D(k)時(shí)，按照下列的方式產(chǎn)生相應(yīng)的新R(k),(k) r (k) r ijk若d：(k 1),(k 1)

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

19、短路徑。D(i, j)：表示i到j(luò)之間的距離。R(i, j):表示i到j(luò)之間的插入點(diǎn)。起始：選定帶權(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)用舉例某個(gè)城市要建立一個(gè)消防站，為該城市所屬的七個(gè)區(qū)服務(wù)，如圖所示。問應(yīng)該把 這個(gè)消防站設(shè)置在

20、哪個(gè)區(qū)，才能使該消防站到最遠(yuǎn)的區(qū)的路徑最短。用Floyd算法求出各點(diǎn)之間的距離，得到表格: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計(jì)算在各點(diǎn)Vi設(shè)立服務(wù)設(shè)施的最大服務(wù)距離S(vi),鼠,)maxdj, i,j 1,2,3.,7。1 j v JS(vi) 10, S(V2