最短路徑問(wèn)題的算法分析及建模案例

-.z最短路徑問(wèn)題的算法分析及建模案例TOC\o"1-3"\h\u12477一.摘要28159二.網(wǎng)絡(luò)最短路徑問(wèn)題的根底知識(shí)28582.1有向圖319722.2連通性4271242.3割集5169532.4最短路問(wèn)題65517三．最短路徑的算法研究6152563.1最短路問(wèn)題的提出630853.2Bellman最短路方程6109753.3Bellman-Ford算法的根本思想7220253.4Bellman-Ford算法的步驟7217903.5實(shí)例7204383.6Bellman-FORD算法的建模應(yīng)用舉例8191263.7Dijkstra算法的根本思想11246233.8Dijkstra算法的理論依據(jù)11307003.9Dijkstra算法的計(jì)算步驟11104763.10Dijstre算法的建模應(yīng)用舉例11274473.11兩種算法的分析13109151.Diklstra算法和Bellman-Ford算法思想有很大的區(qū)別131767Bellman-Ford算法在求解過(guò)程中，每次循環(huán)都要修改所有頂點(diǎn)的權(quán)值，也就是說(shuō)源點(diǎn)到各頂點(diǎn)最短路徑長(zhǎng)度一直要到Bellman-Ford算法完畢才確定下來(lái)。14230862.Diklstra算法和Bellman-Ford算法的限制14166613.Bellman-Ford算法的另外一種理解14244144.Bellman-Ford算法的改良14摘要近年來(lái)計(jì)算機(jī)開(kāi)展迅猛，圖論的研究也得到了很大程度的開(kāi)展，而最短路徑問(wèn)題一直是圖論中的一個(gè)典型問(wèn)題，它已應(yīng)用在地理信息科學(xué)，計(jì)算機(jī)科學(xué)等諸多領(lǐng)域。而在交通路網(wǎng)中兩個(gè)城市之間的最短行車(chē)路線就是最短路徑問(wèn)題的一個(gè)典型例子。由于最短路徑問(wèn)題在各方面廣泛應(yīng)用，以及研究人員對(duì)最短路徑的深入研究，使得在最短路徑問(wèn)題中也產(chǎn)生了很多經(jīng)典的算法。在本課題中我將提出一些最短路徑問(wèn)題的算法以及各算法之間的比擬，最后將這些算法再應(yīng)用于實(shí)際問(wèn)題的建模問(wèn)題中。關(guān)鍵詞：計(jì)算機(jī)圖論交通道路網(wǎng)最短路徑A.Inthispaper,puterdevelopingrapidlyinrecentyears,graphtheoryresearchalsohavebeengreatlydeveloped,andtheshortestpathproblemisatypicalproblemingraphtheory,ithasbeenappliedingeographicalinformationscience,puterscience,andmanyotherfields.Andinthetransportationnetworkoftheshortestroutebetweentwocitiesinisatypicale*ampleoftheshortestpathproblem.Duetotheshortestpathproblemiswidelyusedinvariousaspects,andtheresearchersonthein-depthstudyoftheshortestpath,make

intheshortestpathproblemalsogeneratesalotofclassicalalgorithm.InthistopicI'llsuggestsomealgorithmandthealgorithmoftheshortestpathproblembetweentheparison,finallythealgorithmisappliedtothemodelingoftheactualproblemagain.Keywords:putergraphtrafficroadnetworkTheshortestpath前言最短路徑問(wèn)題是圖論以及運(yùn)籌學(xué)中的一個(gè)非常重要的問(wèn)題，在生產(chǎn)實(shí)踐，運(yùn)輸及工程建筑等方面有著十分廣泛的應(yīng)用。本文對(duì)圖論中的最短路徑問(wèn)題進(jìn)展分析，對(duì)其運(yùn)算解法進(jìn)展分析尋求比擬快捷的模型解法；主要解決的是從*個(gè)頂點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑問(wèn)題。本文從Floyd算法以及Dijkstra算法兩種算法入手，概述了這兩種方法的原理，提出了求解最短路徑問(wèn)題的算法思想，并且對(duì)兩種算法進(jìn)展分析比擬，提出改良的方法。一網(wǎng)絡(luò)最短路徑問(wèn)題的根底知識(shí)圖11.1圖圖G是一個(gè)〔無(wú)向〕圖，其中有序二元組〔V,E〕，V=｛，,...｝是頂點(diǎn)集，E=｛｝是集，是一個(gè)無(wú)序二元組{，}它表示該邊連接的是頂點(diǎn)，。圖1就是一個(gè)圖。注釋?zhuān)簣D形的大小，位置，形狀是無(wú)關(guān)緊要的。假設(shè)={,}則稱(chēng)連接和；點(diǎn)和稱(chēng)為的頂點(diǎn)，和是鄰接的頂點(diǎn)；如果兩條邊有公共的一個(gè)頂點(diǎn)，則稱(chēng)這兩邊是鄰接的。1.2無(wú)環(huán)圖定義：沒(méi)有環(huán)的圖稱(chēng)之為無(wú)環(huán)圖。1.3簡(jiǎn)單圖定義：沒(méi)有環(huán)且沒(méi)有重邊的圖稱(chēng)之為簡(jiǎn)單圖。設(shè)G=〔V,E〕是一個(gè)簡(jiǎn)單圖，則有|E|不大于|V|〔|V|-1〕/21.4完全圖定義：假設(shè)上式的等號(hào)成立則該圖中每對(duì)頂點(diǎn)恰好有一條邊相連，則稱(chēng)該圖為完全圖。1.5有向圖定義：一個(gè)有向圖G是一個(gè)有序二元組〔V,A〕，V=｛，，...,｝是頂點(diǎn)集，A=｛｝稱(chēng)為G的弧集，為有序二元組。稱(chēng)為連向的弧，為的出弧，的入??；稱(chēng)為的得尾，稱(chēng)為aij的頭；稱(chēng)為的前繼，稱(chēng)為的后繼。圖2就是一個(gè)有向圖。圖21.6環(huán)定義：頭尾重合的弧稱(chēng)為環(huán)。1.7簡(jiǎn)單有向圖定義：沒(méi)有環(huán)和重弧的有向圖稱(chēng)為簡(jiǎn)單有向圖。1.8完全有向圖定義：設(shè)G=〔V,E〕是一個(gè)簡(jiǎn)單有向圖，則|A|不大于|V|〔|V|-1〕，假設(shè)等號(hào)成立則稱(chēng)這樣的圖為完全有向圖。1.9途徑，跡，路定義：設(shè)圖G=〔V,E〕，假設(shè)它的*些頂點(diǎn)與邊可以排成一個(gè)非空的有限交織序列〔，，,...,〕,這里該途徑中邊互不一樣，則稱(chēng)為跡；如果頂點(diǎn)互不一樣，則稱(chēng)之為路。顯然路必為跡，但反之不一定成立。1.10連通圖定義：圖G中如果存在一條從頂點(diǎn)到的途徑，則稱(chēng)和是連通的。如果圖G中任何兩個(gè)頂點(diǎn)都是連通的，則稱(chēng)G是連通圖。1.11有向途徑定義：設(shè)有一個(gè)有向圖G=〔V,A〕，G中*些頂點(diǎn)與弧組成的非空有限序列〔，，，，...，，〕這里，...，V，A，且=〔，〕，則稱(chēng)它為從到的有向途徑。類(lèi)似的可定義有向跡，有向路，有向閉途徑，有向閉跡，有向回路〔圈〕等。當(dāng)G時(shí)簡(jiǎn)單有向圖時(shí)，從到的一條有向途徑可簡(jiǎn)記為〔，...,〕。二最短路問(wèn)題定義：所謂最短路徑是指如果從圖中*一頂點(diǎn)〔稱(chēng)為源點(diǎn)〕到達(dá)另一頂點(diǎn)〔稱(chēng)為終點(diǎn)〕的路徑可能不止一條，如何找到一跳有向路徑使得沿這條路徑上各弧的權(quán)值總和最小。2.1最短路問(wèn)題的提出*旅客要從乘飛機(jī)前往奧地利的薩爾斯堡，因?yàn)樗ε鲁俗w機(jī)，因此要選擇一條航線，使得在空中飛行的時(shí)間盡可能的少。如何選擇航線以到達(dá)要求。為此構(gòu)造一個(gè)無(wú)向網(wǎng)絡(luò)總可以化成有向網(wǎng)絡(luò)。設(shè)G=〔V,A,w〕是一個(gè)有向網(wǎng)絡(luò)，p為G中一條有向路，稱(chēng)w〔P〕=為路徑p的路長(zhǎng)?，F(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)，用來(lái)記錄從頂點(diǎn)到該頂點(diǎn)的最短路的長(zhǎng)度〔稱(chēng)為永久標(biāo)號(hào)〕或最短長(zhǎng)度的上界〔稱(chēng)為臨時(shí)標(biāo)號(hào)〕。算法開(kāi)場(chǎng)時(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í)完畢。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)過(guò)S中頂點(diǎn)到達(dá)該頂點(diǎn)的最短路的長(zhǎng)度。3.13Dijkstra算法的計(jì)算步驟最短路徑問(wèn)題是指在一個(gè)賦予權(quán)值的圖的兩個(gè)指定節(jié)點(diǎn)和v之間找出一條具有最小權(quán)值的路。Dijkstra算法是一個(gè)解最短路徑問(wèn)題的算法，這個(gè)算法不僅可以找到最短的〔，v〕，路徑而且可以給出從到圖中所有節(jié)點(diǎn)的最短路徑，根本步驟如下：設(shè)=0，對(duì)所有節(jié)點(diǎn)來(lái)說(shuō)，設(shè)=，并且將標(biāo)號(hào)為0，→t，d為和w之間的權(quán)值〔距離〕。按照每個(gè)沒(méi)有標(biāo)號(hào)的節(jié)點(diǎn)w計(jì)算，，表示節(jié)點(diǎn)t到節(jié)點(diǎn)w之間的權(quán)值。如果標(biāo)號(hào)被修改了說(shuō)明在當(dāng)前得到的到w的最優(yōu)路徑上t和w相鄰，用記錄下來(lái)在所有中選擇一個(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ū)的最短路徑。先寫(xiě)出帶權(quán)鄰接矩陣：W=因?yàn)镚是無(wú)向圖，所以W是對(duì)稱(chēng)矩陣。迭代次數(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í)求得，可由來(lái)查找任何兩個(gè)點(diǎn)之間的最短路徑?！?〕FLOYD算法查找最短路徑的方法：如果，則點(diǎn)是點(diǎn)到點(diǎn)的最短路的中點(diǎn)。用同樣的方法再查找，如果：〔1〕向點(diǎn)查找得：，，...，?！?〕向點(diǎn)查找得：，，...，。則從點(diǎn)到的最短路徑為：，,...,，，，，...，，3.23FLOYD算法的算法步驟Floud算法算法目的：求任意兩個(gè)頂點(diǎn)間的最短路徑。：表示到之間的距離。：表示到之間的插入點(diǎn)。起始：選定帶權(quán)值的鄰接矩陣〔1〕賦值：對(duì)所有的，，，，1?！?〕更新，對(duì)所有的，，如果，則，?！?〕如果=，則算法終止；否則，再次回到〔2〕，以此類(lèi)推。3.24FLOYD建模應(yīng)用舉例