最短路線的最短化

最短路線的最短化

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