最短路線的最短化

最短路線的最短化

1式海斯算法與德國(guó)助力“負(fù)權(quán)”圖自1960年以來(lái)，研究最相關(guān)的問(wèn)題一直成果。其中，荷蘭著名計(jì)算機(jī)專家e.w.dijkas首次提出了賦權(quán)圖（wij0）的有效算法。這一算法可以解決兩個(gè)點(diǎn)之間的最短距離，或者圖g中的點(diǎn)1到其他點(diǎn)之間的最短距離。后來(lái)海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法。但這兩種算法都不能解決含有負(fù)權(quán)的圖的最短路問(wèn)題。因此由Ford提出了Ford算法,它能有效地解決含有負(fù)權(quán)的最短路問(wèn)題。但在現(xiàn)實(shí)生活中,我們所遇到的問(wèn)題大都不含負(fù)權(quán),所以我們?cè)?wij≥0)的情況下選擇Dijkstra算法。定義1若圖G=G(V,E)中各邊e都賦有一個(gè)實(shí)數(shù)W(e),稱為邊e的權(quán),則稱這種圖為賦權(quán)圖,記為G=G(V,E,W)。定義2若圖G=G(V,E)是賦權(quán)圖且W(e)≥0,e∈E(G),若u是vi到vj的路W(u)的權(quán),則稱W(u)為u的長(zhǎng),長(zhǎng)最小的vi到vj的路W(u)稱為最短路。若要找出從v1到vn的通路u,使全長(zhǎng)最短,即minW(u)=∑eij∈uW(e)minW(u)=∑eij∈uW(e)。2vjvk的求取vd在諸多算法中(wij≥0)最經(jīng)典的算法當(dāng)屬Dijkstra算法,該算法的基本思想是動(dòng)態(tài)規(guī)劃最優(yōu)原理,即最短路線上任意兩點(diǎn)間的路線也是最短。因此,若vi到vj的最短路線經(jīng)過(guò)vk,則vi到vk以及vk到vj的部分都是相應(yīng)的最短路線?；静襟E:令s={v1},i=1,ˉs={v2,v3???vn}并令{W(v1)=0Τ(vj)=∞,vj∈ˉs①對(duì)vj∈ˉs,求min{T(vj),W(vi)+wij}=T(vj)。②求minvj∈ˉs{Τ(vj)}得T(vk),使Τ(vk)=minvj∈ˉs{Τ(vj)}令W(vk)=T(vk)③若vk=vn則已找到v1到vn的最短路距離W(vk),否則令i=k從ˉs中刪去vi轉(zhuǎn)①這樣經(jīng)過(guò)有限次迭代則可以求出v1到vn的最短路線,可以用一個(gè)流程圖來(lái)表示:第一步先取W(v1)=0意即v1到v1的距離為0,而T(vj)是對(duì)W(vj)所賦的初值。第二步利用W(v1)已知,根據(jù)min{T(vj),W(vi)+wij}對(duì)T(vj)進(jìn)行修正。第三步對(duì)所有修正后的T(vj)求出其最小者T(vk)。其對(duì)應(yīng)的點(diǎn)vk是v1所能一步到達(dá)的點(diǎn)vj中最近的一個(gè),由于所有W(u)≥0。因此任何從其它點(diǎn)vj中轉(zhuǎn)而到達(dá)vk的通路上的距離都大于v1直接到vk的距離T(vk),因此T(vk)就是v1到vk的最短距離,所以在算法中令W(vk)=T(vk)并從ˉs中刪去vk,若k=n則W(vk)=W(vn)就是v1到vn的最短路線,計(jì)算結(jié)束。否則令vi=vk回到第二步,繼續(xù)運(yùn)算,直到k=n為止。這樣每一次迭代,得到v1到一點(diǎn)vk的最短距離,重復(fù)上述過(guò)程直到vk=vn。3vtvj計(jì)算設(shè)6個(gè)城市v1,v2,…,v6之間的一個(gè)公路網(wǎng)(圖1)每條公路為圖中的邊,邊上的權(quán)數(shù)表示該段公路的長(zhǎng)度(單位:百公里),設(shè)你處在城市v1,那么從v1到v6應(yīng)選擇哪一路徑使你的費(fèi)用最省。解:首先設(shè)每百公里所用費(fèi)用相同,求v1到v6的費(fèi)用最少,既求v1到v6的最短路線。為了方便計(jì)算,先作出該網(wǎng)絡(luò)的距離矩陣,如下:L=[v1v2v3v4v5v6v1052∞∞∞v250159∞v3210810∞v4∞58025v5∞910202v6∞∞∞520](0)設(shè)W(v1)=0,Τ(v)=∞,vj∈ˉs={v2,v3,v4,v5,v6}?(1)第一次迭代①計(jì)算T(vj),j=2,3,4,5,6如下T(v2)=min{T(v2),W(v1)+w12}=min{∞,0+5}=5T(v3)=min{T(v3),W(v1)+w13}=min{∞,0+2}=2T(v4)=min{T(v4),W(v1)+w14}=min{∞,0+∞}=∞T(v5)=∞,T(v6)=∞②取minvj∈ˉs{Τ(vj)}=2=Τ(v3),令W(v3)=T(v3)=2③由于k=3≠(n=6),令ˉs={v2,v4,v5,v6},i=3轉(zhuǎn)(1)第二次迭代:①算T(vj),j=2,4,5,6如下T(v2)=min{T(v2),W(v3)+w23}=min{5,2+1}=3T(v4)=min{T(v4),W(v3)+w34}=min{8,2+8}=8T(v5)=min{T(v5),W(v3)+w35}=min{10,2+10}=10T(v6)=min{T(v6),W(v3)+w36}=min{∞,2+∞}=∞②取minvj∈ˉs{Τ(vj)}=3=Τ(v2)令W(v2)=T(v2)=3③由于k=2≠(n=6),令ˉs={v4,v5,v6}i=2轉(zhuǎn)(1)第三次迭代:①算T(vj),j=4,5,6如下Τ(v4)=min{Τ(v4),W(v2)+w24}=min{8,3+5}=8Τ(v5)=min{Τ(v5),W(v2)+w25}=min{10,3+9}=10Τ(v6)=∞②minvj∈ˉs{Τ(vj)}=8=Τ(v4)?W(v4)=Τ(v4)=8③由于k=4≠(n=6),令ˉs={v5,v6}i=4轉(zhuǎn)(1)第四次迭代:①算T(vj),j=5,6如下T(v5)=min{T(v5),W(v4)+w45}=min{10,2+8}=10T(v6)=min{T(v6),W(v4)+w46}=min{∞,8+5}=13②取minvj∈ˉs{Τ(vj)}=10=Τ(v5),令W(v5)=T(v5)=10③由于k=5≠(n=6),令ˉs={v6}轉(zhuǎn)(1)第五次迭代:①算T(vj),j=6如下T(v6)=min{T(v