最短路线的最短化

最短路线的最短化

1式海斯算法与德国助力“负权”图自1960年以来，研究最相关的问题一直成果。其中，荷兰著名计算机专家e.w.dijkas首次提出了赋权图（wij0）的有效算法。这一算法可以解决两个点之间的最短距离，或者图g中的点1到其他点之间的最短距离。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在(wij≥0)的情况下选择Dijkstra算法。定义1若图G=G(V,E)中各边e都赋有一个实数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)最经典的算法当属Dijkstra算法,该算法的基本思想是动态规划最优原理,即最短路线上任意两点间的路线也是最短。因此,若vi到vj的最短路线经过vk,则vi到vk以及vk到vj的部分都是相应的最短路线。基本步骤:令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转①这样经过有限次迭代则可以求出v1到vn的最短路线,可以用一个流程图来表示:第一步先取W(v1)=0意即v1到v1的距离为0,而T(vj)是对W(vj)所赋的初值。第二步利用W(v1)已知,根据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回到第二步,继续运算,直到k=n为止。这样每一次迭代,得到v1到一点vk的最短距离,重复上述过程直到vk=vn。3vtvj计算设6个城市v1,v2,…,v6之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市v1,那么从v1到v6应选择哪一路径使你的费用最省。解:首先设每百公里所用费用相同,求v1到v6的费用最少,既求v1到v6的最短路线。为了方便计算,先作出该网络的距离矩阵,如下: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