最短路问题-D算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最 短 路 问 题,一、问题的提法及应用背景,（1）问题的提法,寻求网络中两点间的最短路就是寻求连接这两个点的边的,总权数最小的,通路,。（注意：在有向图中，通路,开的初等链,中所有的弧应是,首尾相连,的。）,（2）应用背景,管道铺设、线路安排、厂区布局、设备更新等。,二、最短路算法,1,D,氏标号法（,Dijkstra,）；边权非负,2. 列表法（福德法）；有负权，无负回路,4,v,1,v,2,v,3,v,4,v,6,v,5,v,7,2,2,5,6,1,4,1,3,4,1,2,1D,氏标号法（,Dijkstra,）,（1）求解思路,从始点出发，逐步,顺序地向外探寻,，,每向外延伸一步都要求是,最短的。,（2）使用条件,网络中,所有的弧权,均,非负,，即 。,（3）选用符号的意义,：,P,标号,（,Permanent,固定/永久性标号）,从始点到该标号点的最短路权,T,标号,（,Temporary,临时性标号）,从始点到该标号点的最短路权,上界,（4）计算步骤及例子：,第一步,：给起始点v,1,标上固定标号 , 其余各点标临时性标号,T,(,v,j,)=,j,1,;,=,l,1,j,第二步,：考虑满足如下条件的所有点,与,v,1,相邻的点，即 ;, 具有,T,标号，即 ，,为,T,标号点集.,修改 的,T,标号为 ，并将结果仍记为,T,(,v,j,)。,s,v,j,若网络图中已无满足此条件的,T,标号点，停止计算。,第三步,： 令 , 然后,将 的,T,标号改成,P,标号,，转入第二步。此时，,要注意将第二步中的 改为,。,例一、 用Dijkstra算法求下图从v,1,到v,6,的最短路。,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,解,（1）首先给,v,1,以P标号，给其余所有点T标号。,（2）,例一、 用Dijkstra算法求下图从v,1,到v,6,的最短路。,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,（4）,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,（5）,（6）,反向追踪得v,1,到v,6,的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从,1,到,8,的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,min d,12,d,14,d,16,=min 0+2,0+1,0+3=min 2,1,3=1,X=1,4, p,4,=1,p,4,=1,p,1,=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min d,12,d,16,d,42,d,47,=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2,X=1,2,4, p,2,=2,p,1,=0,p,4,=1,p,2,=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min d,16,d,23,d,25,d,47,=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3,X=1,2,4,6, p,6,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min d,23,d,25,c,47,d,67,=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,X=1,2,4,6,7, p,7,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d,23,d,25,d,75,d,78,=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6,X=1,2,4,5,6,7, p,5,=6,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min d,23,d,53,d,58,d,78,=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8,X=1,2,3,4,5,6,7, p,3,=8,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min d,38,d,58,d,78,=min 8+6,6+4,3+7=min 14,10,11=10,X=1,2,3,4,5,6,7,8, p,8,=10,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,