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

最短路徑問題的算法分析及建模案例最短路徑問題的算法分析及建模案例TOC\o"1-3"\h\u12477一.摘要 38159二.網(wǎng)絡(luò)最短路徑問題的基礎(chǔ)知識(shí) 58582.1有向圖 719722.2連通性 錯(cuò)誤!未定義書簽。271242.3割集 錯(cuò)誤!未定義書簽。169532.4最短路問題 85517三．最短路徑的算法研究 錯(cuò)誤!未定義書簽。152563.1最短路問題的提出 930853.2Bellman最短路方程 錯(cuò)誤!未定義書簽。109753.3Bellman-Ford算法的基本思想 錯(cuò)誤!未定義書簽。220253.4Bellman-Ford算法的步驟 錯(cuò)誤!未定義書簽。217903.5實(shí)例 錯(cuò)誤!未定義書簽。204383.6Bellman-FORD算法的建模應(yīng)用舉例 錯(cuò)誤!未定義書簽。191263.7Dijkstra算法的基本思想 9246233.8Dijkstra算法的理論依據(jù) 9307003.9Dijkstra算法的計(jì)算步驟 9104763.10Dijstre算法的建模應(yīng)用舉例 10274473.11兩種算法的分析 錯(cuò)誤!未定義書簽。109151.Diklstra算法和Bellman-Ford算法思想有很大的區(qū)別 錯(cuò)誤!未定義書簽。1767Bellman-Ford算法在求解過程中，每次循環(huán)都要修改所有頂點(diǎn)的權(quán)值，也就是說源點(diǎn)到各頂點(diǎn)最短路徑長(zhǎng)度一直要到Bellman-Ford算法結(jié)束才確定下來。 錯(cuò)誤!未定義書簽。230862.Diklstra算法和Bellman-Ford算法的限制 錯(cuò)誤!未定義書簽。166613.Bellman-Ford算法的另外一種理解 錯(cuò)誤!未定義書簽。244144.Bellman-Ford算法的改進(jìn) 錯(cuò)誤!未定義書簽。摘要近年來計(jì)算機(jī)發(fā)展迅猛，圖論的研究也得到了很大程度的發(fā)展，而最短路徑問題一直是圖論中的一個(gè)典型問題，它已應(yīng)用在地理信息科學(xué)，計(jì)算機(jī)科學(xué)等諸多領(lǐng)域。而在交通路網(wǎng)中兩個(gè)城市之間的最短行車路線就是最短路徑問題的一個(gè)典型例子。由于最短路徑問題在各方面廣泛應(yīng)用，以及研究人員對(duì)最短路徑的深入研究，使得在最短路徑問題中也產(chǎn)生了很多經(jīng)典的算法。在本課題中我將提出一些最短路徑問題的算法以及各算法之間的比較，最后將這些算法再應(yīng)用于實(shí)際問題圖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簡(jiǎn)單圖定義：沒有環(huán)且沒有重邊的圖稱之為簡(jiǎn)單圖。設(shè)G=（V,E）是一個(gè)簡(jiǎn)單圖，則有|E|不大于|V|（|V|-1）/21.4完全圖定義：若上式的等號(hào)成立那么該圖中每對(duì)頂點(diǎn)恰好有一條邊相連，則稱該圖為完全圖。1.5有向圖定義：一個(gè)有向圖G是一個(gè)有序二元組（V,A），V=｛，，...,｝是頂點(diǎn)集，A=｛｝稱為G的弧集，為有序二元組。稱為連向的弧，為的出弧，的入?。环Q為的得尾，稱為aij的頭；稱為的前繼，稱為的后繼。圖2就是一個(gè)有向圖。圖21.6環(huán)定義：頭尾重合的弧稱為環(huán)。1.7簡(jiǎn)單有向圖定義：沒有環(huán)和重弧的有向圖稱為簡(jiǎn)單有向圖。1.8完全有向圖定義：設(shè)G=（V,E）是一個(gè)簡(jiǎn)單有向圖，則|A|不大于|V|（|V|-1），若等號(hào)成立則稱這樣的圖為完全有向圖。1.9途徑，跡，路定義：設(shè)圖G=（V,E），若它的某些頂點(diǎn)與邊可以排成一個(gè)非空的有限交錯(cuò)序列（，，,...,）,這里該途徑中邊互不相同，則稱為跡；如果頂點(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í)簡(jiǎn)單有向圖時(shí)，從到的一條有向途徑可簡(jiǎn)記為（，...,）。二最短路問題定義：所謂最短路徑是指如果從圖中某一頂點(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è)有向網(wǎng)絡(luò)，p為G中一條有向路，稱w（P）=為路徑p的路長(zhǎng)。現(xiàn)找網(wǎng)絡(luò)中一條從指定頂點(diǎn)vi到另一個(gè)指定頂點(diǎn)vj的最短有向路徑。三最短路徑算法研究3.1Dijkstra算法3.11Dijkstra算法的基本思想對(duì)網(wǎng)絡(luò)中每個(gè)頂點(diǎn)賦一個(gè)標(biāo)號(hào)，用來記錄從頂點(diǎn)到該頂點(diǎn)的最短路的長(zhǎng)度（稱為永久標(biāo)號(hào)）或最短長(zhǎng)度的上界（稱為臨時(shí)標(biāo)號(hào)）。算法開始時(shí)，只有頂點(diǎn)被賦予永久標(biāo)號(hào)=0，其他頂點(diǎn)賦予臨時(shí)標(biāo)號(hào)。一般的，算法在被臨時(shí)標(biāo)號(hào)的頂點(diǎn)中尋找一個(gè)頂點(diǎn)，其臨時(shí)標(biāo)號(hào)最小，然后將賦予永久標(biāo)號(hào)，并且對(duì)其余臨時(shí)標(biāo)號(hào)的頂點(diǎn)vj按照方式修正其標(biāo)號(hào)。算法在所有頂點(diǎn)被賦予永久標(biāo)號(hào)時(shí)結(jié)束。3.12Dijkstra算法的理論依據(jù)對(duì)于S中任意一頂點(diǎn)，其永久標(biāo)號(hào)都是從頂點(diǎn)到該頂點(diǎn)的最短路的長(zhǎng)度。對(duì)于R中任意一頂點(diǎn)，其臨時(shí)標(biāo)號(hào)都是從頂點(diǎn)出發(fā)，只經(jīng)過S中頂點(diǎn)到達(dá)該頂點(diǎn)的最短路的長(zhǎng)度。3.13Dijkstra算法的計(jì)算步驟最短路徑問題是指在一個(gè)賦予權(quán)值的圖的兩個(gè)指定節(jié)點(diǎn)和v之間找出一條具有最小權(quán)值的路。Dijkstra算法是一個(gè)解最短路徑問題的算法，這個(gè)算法不僅可以找到最短的（，v），路徑而且可以給出從到圖中所有節(jié)點(diǎn)的最短路徑，基本步驟如下：設(shè)=0，對(duì)所有節(jié)點(diǎn)來說，設(shè)=，并且將標(biāo)號(hào)為0，→t，d為和w之間的權(quán)值（距離）。按照每個(gè)沒有標(biāo)號(hào)的節(jié)點(diǎn)w計(jì)算，，表示節(jié)點(diǎn)t到節(jié)點(diǎn)w之間的權(quán)值。如果標(biāo)號(hào)被修改了說明在當(dāng)前得到的到w的最優(yōu)路徑上t和w相鄰，用記錄下來在所有中選擇一個(gè)最小的即，w未標(biāo)號(hào)。將s標(biāo)號(hào)為/，表示節(jié)點(diǎn)到s的最優(yōu)路徑的長(zhǎng)度且與s相鄰。如果重點(diǎn)v已經(jīng)標(biāo)號(hào)，則停止。得到一條從到v的最優(yōu)路徑。否則s→t，反向。按照上述步驟繼續(xù)計(jì)算。3.14Dijstre算法的建模應(yīng)用舉例某城市要在該城市所轄的8個(gè)區(qū)中的區(qū)建立一個(gè)取水點(diǎn)，如圖所示的是這8個(gè)區(qū)之間的分布以及相鄰各區(qū)的距離?，F(xiàn)要從區(qū)向其他各區(qū)運(yùn)水，求出區(qū)到其他各區(qū)的最短路徑。先寫出帶權(quán)鄰接矩陣：W=因?yàn)镚是無向圖，所以W是對(duì)稱矩陣。迭代次數(shù)1020218328104831058610126710127912812最后標(biāo)記L（v）021736912Z（v）因此得到最短路徑為：迭代次數(shù)最后標(biāo)記L（v）021736912Z（v）由上表可得到到各點(diǎn)的最短路徑為：；；，，；；；，，；，。上述Dijkstra算法的MATLAB代碼：w=[0218infinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);%賦初值%fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1;whilek<n%更新l(v)和z(v)%fori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendl,z%求v*L1=1;fori=1:nforj=1:kifi~=s(j)l1(i)=l1(i);elsel1(i)=inf;endendendlv=inf;fori=1:nifl1(i)<lvlv=l1(i);v=i;endendlv,vs(k+1)=vk=k+1u=s(k)endl,z3.2FLOYD算法3.21FLOYD算法的基本思想直接在圖的帶權(quán)鄰接矩陣中使用插入頂點(diǎn)的方法依次構(gòu)造出n個(gè)矩陣，...，，使得最終得到的矩陣成為圖的距離矩陣，并且同時(shí)求出插入的點(diǎn)的矩陣以便于得到兩點(diǎn)間的最短路徑。3.22FLOYD算法原理（1）FLOYD算法求路徑矩陣的方法：在建立距離矩陣的同時(shí)可建立路徑矩陣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.23FLOYD算法的算法步驟Floud算法算法目的：求任意兩個(gè)頂點(diǎn)間的最短路徑。：表示到之間的距離。：表示到之間的插入點(diǎn)。起始：選定帶權(quán)值的鄰接矩陣（1）賦值：對(duì)所有的，，，，1。（2）更新，對(duì)所有的，，如果，那么，。（3）如果=，那么算法終止；否則，再次回到（2），以此類推。3.24FLOYD建模應(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;inf,inf,inf,1.5,0];[d,r]=floyd(w)S=max(d’)%求矩陣各列的最大值s=min(S)3.