1、 最短路徑問題的算法分析及建模案例一.摘要2二.網(wǎng)絡(luò)最短路徑問題的基礎(chǔ)知識22.1有向圖32.2連通性42.3割集52.4最短路問題6三最短路徑的算法研究63.1最短路問題的提出63.2 Bellman最短路方程63.3 Bellman-Ford算法的基本思想73.4 Bellman-Ford算法的步驟73.5實(shí)例73.6 Bellman-FORD算法的建模應(yīng)用舉例83.7 Dijkstra算法的基本思想113.8 Dijkstra算法的理論依據(jù)113.9 Dijkstra算法的計(jì)算步驟113.10 Dijstre算法的建模應(yīng)用舉例113.11 兩種算法的分析131.Diklstra算法和Be

2、llman-Ford算法思想有很大的區(qū)別13Bellman-Ford算法在求解過程中，每次循環(huán)都要修改所有頂點(diǎn)的權(quán)值，也就是說源點(diǎn)到各頂點(diǎn)最短路徑長度一直要到Bellman-Ford算法結(jié)束才確定下來。142.Diklstra算法和Bellman-Ford算法的限制143.Bellman-Ford算法的另外一種理解144.Bellman-Ford算法的改進(jìn)14 摘要 近年來計(jì)算機(jī)發(fā)展迅猛，圖論的研究也得到了很大程度的發(fā)展，而最短路徑問題一直是圖論中的一個(gè)典型問題，它已應(yīng)用在地理信息科學(xué)，計(jì)算機(jī)科學(xué)等諸多領(lǐng)域。而在交通路網(wǎng)中兩個(gè)城市之間的最短行車路線就是最短路徑問題的一個(gè)典型例子。 由于最短路徑

3、問題在各方面廣泛應(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 developed, and the shortest path problem is a typical problem in gr

4、aph 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 problem.Due to the shortest path problem is widely used in various asp

5、ects, 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 I'll suggest some algorithm and the algorithm of the shortest path problem between the comparison, finally the algorithm is appl

6、ied 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算法以及Dijkstra算法兩種算法入手，概述了這兩種方法的原理，提出了求解最短路徑問題的算法思想，并且對兩種算法進(jìn)行

7、分析比較，提出改進(jìn)的方法。一 網(wǎng)絡(luò)最短路徑問題的基礎(chǔ)知識 圖11.1 圖 圖G是一個(gè)（無向）圖，其中有序二元組（V,E），V=，,.是頂點(diǎn)集，E=是集，是一個(gè)無序二元組，它表示該邊連接的是頂點(diǎn)，。圖1就是一個(gè)圖。 注釋：圖形的大小，位置，形狀是無關(guān)緊要的。若=,則稱連接和；點(diǎn)和稱為的頂點(diǎn)，和是鄰接的頂點(diǎn)；如果兩條邊有公共的一個(gè)頂點(diǎn)，則稱這兩邊是鄰接的。1.2 無環(huán)圖定義：沒有環(huán)的圖稱之為無環(huán)圖。1.3 簡單圖定義：沒有環(huán)且沒有重邊的圖稱之為簡單圖。設(shè)G=（V,E）是一個(gè)簡單圖，則有|E|不大于|V|（|V|-1）/21.4 完全圖定義：若上式的等號成立那么該圖中每對頂點(diǎn)恰好有一條邊相連，則稱該

8、圖為完全圖。1.5 有向圖定義：一個(gè)有向圖G是一個(gè)有序二元組（V,A），V=，.,是頂點(diǎn)集，A=稱為G的弧集，為有序二元組。稱為連向的弧，為的出弧，的入??；稱為的得尾，稱為aij的頭；稱為的前繼，稱為的后繼。圖2就是一個(gè)有向圖。 圖21.6 環(huán)定義：頭尾重合的弧稱為環(huán)。1.7 簡單有向圖定義：沒有環(huán)和重弧的有向圖稱為簡單有向圖。1.8 完全有向圖定義：設(shè)G=（V,E）是一個(gè)簡單有向圖，則|A|不大于|V|（|V|-1），若等號成立則稱這樣的圖為完全有向圖。1.9 途徑，跡，路定義：設(shè)圖G=（V,E），若它的某些頂點(diǎn)與邊可以排成一個(gè)非空的有限交錯(cuò)序列（，,.,）,這里該途徑中邊互不相同，則稱為跡

9、；如果頂點(diǎn)互不相同，則稱之為路。顯然路必為跡，但反之不一定成立。1.10 連通圖定義：圖G中如果存在一條從頂點(diǎn)到的途徑，則稱和是連通的。如果圖G中任何兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖。1.11 有向途徑定義：設(shè)有一個(gè)有向圖G=（V,A），G中某些頂點(diǎn)與弧組成的非空有限序列（，.，）這里，.，V，A，且=（，），則稱它為從到的有向途徑。類似的可定義有向跡，有向路，有向閉途徑，有向閉跡，有向回路（圈）等。當(dāng)G時(shí)簡單有向圖時(shí)，從到的一條有向途徑可簡記為（，.,）。二 最短路問題定義：所謂最短路徑是指如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一跳有向路徑使得沿

10、這條路徑上各弧的權(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è)有向網(wǎng)絡(luò)，p為G中一條有向路，稱w（P）=為路徑p的路長?，F(xiàn)找網(wǎng)絡(luò)中一條從指定頂點(diǎn)vi到另一個(gè)指定頂點(diǎn)vj的最短有向路徑。三 最短路徑算法研究3.1 Dijkstra算法3.11 Dijkstra算法的基本思想對網(wǎng)絡(luò)中每個(gè)頂點(diǎn)賦一個(gè)標(biāo)號，用來記錄從頂點(diǎn)到該頂點(diǎn)的最短路的長度（稱為永久標(biāo)號）或最短長度的上界（稱為臨時(shí)標(biāo)號）。算法開始時(shí)，只有頂點(diǎn)

11、被賦予永久標(biāo)號=0，其他頂點(diǎn)賦予臨時(shí)標(biāo)號。一般的，算法在被臨時(shí)標(biāo)號的頂點(diǎn)中尋找一個(gè)頂點(diǎn)，其臨時(shí)標(biāo)號最小，然后將賦予永久標(biāo)號，并且對其余臨時(shí)標(biāo)號的頂點(diǎn)vj按照方式修正其標(biāo)號。算法在所有頂點(diǎn)被賦予永久標(biāo)號時(shí)結(jié)束。3.12 Dijkstra算法的理論依據(jù)（1） 對于S中任意一頂點(diǎn)，其永久標(biāo)號都是從頂點(diǎn)到該頂點(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)和v之間找出一條具有最小權(quán)值的路。Dijkstra算法是一個(gè)解最短路徑問題的算法，這個(gè)算法不僅可以

12、找到最短的（，v），路徑而且可以給出從到圖中所有節(jié)點(diǎn)的最短路徑，基本步驟如下：（1） 設(shè)=0，對所有節(jié)點(diǎn)來說，設(shè)=，并且將標(biāo)號為0，t，d為和w之間的權(quán)值（距離）。（2） 按照每個(gè)沒有標(biāo)號的節(jié)點(diǎn)w計(jì)算，表示節(jié)點(diǎn)t到節(jié)點(diǎn)w之間的權(quán)值。如果標(biāo)號被修改了說明在當(dāng)前得到的到w的最優(yōu)路徑上t和w相鄰，用記錄下來在所有中選擇一個(gè)最小的即，w未標(biāo)號。將s標(biāo)號為/，表示節(jié)點(diǎn)到s的最優(yōu)路徑的長度且與s相鄰。（3） 如果重點(diǎn)v已經(jīng)標(biāo)號，則停止。得到一條從到v的最優(yōu)路徑。否則st，反向。（4） 按照上述步驟繼續(xù)計(jì)算。3.14 Dijstre算法的建模應(yīng)用舉例某城市要在該城市所轄的8個(gè)區(qū)中的區(qū)建立一個(gè)取水點(diǎn)，如圖所示

13、的是這8個(gè)區(qū)之間的分布以及相鄰各區(qū)的距離?，F(xiàn)要從區(qū)向其他各區(qū)運(yùn)水，求出區(qū)到其他各區(qū)的最短路徑。先寫出帶權(quán)鄰接矩陣：W=因?yàn)镚是無向圖，所以W是對稱矩陣。迭代次數(shù) 1020218328104831058610126710127912812最后標(biāo)記L（v）021736912Z（v）因此得到最短路徑為：迭代次數(shù) 最后標(biāo)記L（v）021736912Z（v）由上表可得到到各點(diǎn)的最短路徑為：；，；，；，。上述Dijkstra算法的MATLAB代碼：w=0 2 1 8 inf inf inf;2 0 inf 6 1 inf inf inf ;1 inf 0 7 inf inf 9 inf;8 6 7 0 5

14、 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0n=size(w,1);w1=w(1,:); %賦初值%for i=1:nl(i)=w1(i);z(i)=1;ends=;s(1)=1;u=s(1);k=1;while k<n %更新l(v)和z(v) %for i=1:nfor j=1:kif i=s(j)if l(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u; end end endendl,z %求v*

15、L1=1;for i=1:nfor j=1:kif i=s(j)l1(i)=l1(i);elsel1(i)=inf; end endendlv=inf;for i=1:nif l1(i)<lvlv=l1(i);v=i;endendlv,vs(k+1)=vk=k+1u=s(k)endl,z3.2 FLOYD算法3.21 FLOYD算法的基本思想 直接在圖的帶權(quán)鄰接矩陣中使用插入頂點(diǎn)的方法依次構(gòu)造出n個(gè)矩陣，.，使得最終得到的矩陣成為圖的距離矩陣，并且同時(shí)求出插入的點(diǎn)的矩陣以便于得到兩點(diǎn)間的最短路徑。3.22 FLOYD算法原理（1）FLOYD算法求路徑矩陣的方法：在建立距離矩陣的同時(shí)可建立

16、路徑矩陣R。每一次求到一個(gè)時(shí)，按照下列的方式產(chǎn)生相應(yīng)的新，即當(dāng)被插入在任何兩點(diǎn)間的最短路徑時(shí)，被記錄在中，依次求時(shí)求得，可由來查找任何兩個(gè)點(diǎn)之間的最短路徑。（2）FLOYD算法查找最短路徑的方法：如果，那么點(diǎn)是點(diǎn)到點(diǎn)的最短路的中點(diǎn)。用同樣的方法再查找，如果：（1）向點(diǎn)查找得：，.，。（2）向點(diǎn)查找得：，.，。那么從點(diǎn)到的最短路徑為：，,.,，.，3.23 FLOYD算法的算法步驟Floud算法算法目的：求任意兩個(gè)頂點(diǎn)間的最短路徑。：表示到之間的距離。：表示到之間的插入點(diǎn)。起始：選定帶權(quán)值的鄰接矩陣（1）賦值：對所有的，1。（2）更新，對所有的，如果，那么，。（3）如果=，那么算法終止；否則，再

17、次回到（2），以此類推。3.24 FLOYD建模應(yīng)用舉例某個(gè)城市要建立一個(gè)消防站，為該城市所屬的七個(gè)區(qū)服務(wù)，如圖所示。問應(yīng)該把這個(gè)消防站設(shè)置在哪個(gè)區(qū)，才能使該消防站到最遠(yuǎn)的區(qū)的路徑最短。用Floyd算法求出各點(diǎn)之間的距離，得到表格：0351075.57302742.54520524.5610750378.57423045.55.52.54.57401.57468.55.51.50從上表可以得出距離矩陣計(jì)算在各點(diǎn)設(shè)立服務(wù)設(shè)施的最大服務(wù)距離，。，由于=那么應(yīng)該將消防站設(shè)置在處。上述Floyd算法的MATLAB算法代碼為：clear：w=0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;