数学建模迪杰斯特拉算法例题

1、 数学建模专题练习 迪杰斯特拉算法 2014.09例一、例一、 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。 v1v2v3v4v6v5352242421 解解 （1）首先给v1以P标号，给其余所有点T标号。0)(1vP)6, 3,2()(ivTi（2）330,min)(, )(min)(12122lvPvTvT550,min)(, )(min)(13133lvPvTvT3)(, 3)()(),(),(),(),(min)(min2265432vpvTvTvTvTvTvTvTjsvj所以有， v1v2v3v4v6v5352242421（4）4 13,5min)(,

2、 )(min)(23233lvPvTvT523,min)(, )(min)(24244lvPvTvT523,min)(, )(min)(25255lvPvTvT4)(, 4)()(),(),(),(min)(min336543vpvTvTvTvTvTvTjsvj所以有，v1v2v3v4v6v5352242421（5）544,5min)(, )(min)(35355lvPvTvT725, 45,min)(,)(, )(min)(56546466lvPlvPvTvT（6）反向追踪得v1到v6的最短路为：6521vvvv5)(, 5)(, 5)()()(),(),(min)(min5454654vp

3、vpvTvTvTvTvTvTjsvj所以有，7)(, 7)(min)(min66vpvTvTjsvj所以有，237184566134105275934682例二例二. .求从求从1到到8的最短路径的最短路径237184566134105275934682X=1min d12,d14,d16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, p4=1p4=1p1=0237184566134105275934682X=1,4min d12,d16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, p2=2p1=0p4=1p2=

4、2237184566134105275934682X=1,2,4min d16,d23,d25,d47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, p6=3p2=2p4=1p1=0p6=3237184566134105275934682X=1,2,4,6min d23,d25,c47,d67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X=1,2,4,6,7min d23,d25,d75,d78=min 2+

5、6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X=1,2,4,6,7min d23,d53,d58,d78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X=1,2,3,4,6,7min d38,d58,d78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2

6、,3,4,5,6,7,8, p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10例三例三. 下图为单行线交通网，每弧旁的数字表示通过这下图为单行线交通网，每弧旁的数字表示通过这条条 线所需的费用。现在某人要从线所需的费用。现在某人要从v1出发，通过这个交出发，通过这个交 通网到通网到v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1v4v6

7、121061210v8v9v72363从从v1到到v8：P1=（v1，v2，v5，v8） 费用费用 6+1+6=13P2=（v1，v3，v4， v6， v7， v8） 费用费用 3+2+10+2+4=21P3= 从从v1到到v8的旅行路线的旅行路线 从从v1到到v8的路。的路。旅行路线总费用旅行路线总费用 路上所有弧权之和。路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。最短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最短路问题最短路问题 给定有向网络给定有向网络D=（V，A，W），任意弧），任意弧aijA，有权有权w（ aij

8、 ）=wij，给定，给定D中的两个顶点中的两个顶点vs，vt。设。设P是是D中从中从vs到到vt的一条路，定义路的一条路，定义路P的权（长度）是的权（长度）是P中中所有弧的权之和，记为所有弧的权之和，记为w（P）。最短路问题就是要在）。最短路问题就是要在所有从所有从vs到到vt的路中，求一条路的路中，求一条路P0 ，使，使(P)min)(PP0ww 称称P0是从是从vs到到vt的最短路。路的最短路。路P0的权称为从的权称为从vs到到vt的路长。记为的路长。记为ust。 当所有当所有 wij 0 时，时，本算法是用来本算法是用来求给定点求给定点vs到到任一个点任一个点vj 最短路最短路的公认的最

9、好方法。的公认的最好方法。事实：如果事实：如果P是是D中从中从vs到到vj的最短路，的最短路，vi是是P中的一中的一个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到 vi的最短路。的最短路。 最短路的子路也是最短路。最短路的子路也是最短路。思想：将思想：将D=（V，A，W）中）中vs到所有其它顶点的最短到所有其它顶点的最短 路按其路按其路长路长从小到大排列为：从小到大排列为：u0 u1 u2 unu0表示表示vs到自身的长度，相应最短路记为：到自身的长度，相应最短路记为：P0，P1，P2，Pn， sivswu,vi0X1000min , XVX X 则则记记取最小值的点为

10、取最小值的点为v1， P1=P（vs，v1） 假定假定 u0，u1，uk的值已求出，对应的最短路的值已求出，对应的最短路分别为分别为P1=P（vs，v1），）， P2=P（vs，v2），）， Pk=P（vs，vk）P1一定只有一条弧。一定只有一条弧。 记记 kkkskvvvvXVX , ,.,X21 则则 ) ,w(miniXX1vvuuivvkkki 使上式达到最小值的点使上式达到最小值的点v 可取为可取为vk+1。 计算过程中可采用标号方法。计算过程中可采用标号方法。 Xk中的点，中的点，ui 值是值是vs 到到vi 的最短路长度，相应的最短路长度，相应的点记的点记“永久永久”标号；标号；

11、 XK中的点，中的点，ui值是值是vs到到vi的最短路长度的上界，的最短路长度的上界，相应的点记相应的点记“临时临时”标号，供进一步计算使用。标号，供进一步计算使用。前点标号前点标号 i : 表示点表示点vs到到vj的最短路上的最短路上vj的前一点。的前一点。如如 i=m，表示，表示vs到到vj的最短路上的最短路上vj前一点是前一点是vm。 1,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v6

12、0,01, 1, 1,11, 1, 1, 1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,3图上标号法图上标号法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,31,6图上标号法图上标号法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,33,5图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363

13、v60,01, 4,111,11, 1, 1,31, 图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11, 2,61, 1,31,图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11, 2,61, 1,31,图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9

14、v72363v60,05,101,11, 2,65,121,35,9图上标号法图上标号法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,9图上标号法图上标号法:Dijkstra算法步骤：算法步骤：第第1步：令步：令us= 0，uj=wsj （1jn）若）若asj A，则，则第第2步：步：(选永久标号选永久标号)在在XK中选一点中选一点vi，满足，满足 第第3步：（给点步：（给点vi永久性标号）永久性标号） 第第4步：步：(修改临时标号修改临时标号)对所有对所有 如果如果 , Xv 1kj jijiuwu 令令

15、 j=i，uj=ui+wij否则否则, i,uj 不变不变,把把k换成换成k+1，返回第返回第2步。步。 jXviuminu Kj 如果如果ui=+ ，停止，停止，令令Xk+1= Xkvi,Xk+1= Xkvi令令wsj=+ , X0=vs ,X0=VX0 ,k=0, i=0 (0 jn）从从vs到到XK中各点没有路；否则，转第中各点没有路；否则，转第3步。步。如果如果Xk+1 = ，结束，到所有的点的最短路已经求结束，到所有的点的最短路已经求得得 ；否则，转第；否则，转第4步。步。例三例三. 用用Dijkstra算法求前面例子中从算法求前面例子中从v1到各点的最短到各点的最短路。路。解：解：

16、u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+ ， j=1 （j=2，3，9）X0=v1 ，X0=v2，v3，v9v2v523464v3v1v4v6121061210v8v9v72363K=0 minu2，u3，u4，u5，u6，u7，u8，u9 =min6，3，1， ， ， ， ， =1= u4 点点v4得永久标号，得永久标号， 4=1 ，X1=v1，v4， X1=v2，v3， v5，v6 ，v7，v8 ，v9，在所有在所有vjX1中，中， u6= ，u4+w46=1+10=11， 即即 u4+w46 u6 修改临时标号修改临时标号u6= 11 ， 6=4 ，其余标

17、号不变。，其余标号不变。v2v523464v3v1v4v6121061210v8v9v72363K=0 +1=1 minu2，u3，u5，u6，u7，u8，u9 =min6，3， ， 11， ， ， =3= u3 点点v3得永久标号，得永久标号， 3=1 ，X2=v1，v4 ，v3， X2=v2， v5，v6 ，v7，v8 ，v9， u2= 6 ，u3+w32=3+2=5， 即即 u3+w32 u2 修改临时标号修改临时标号u2= 5 ， 2=3 ，其余标号不变。，其余标号不变。在所有在所有vjX2中中， k=2 +1=3 minu5，u6，u7，u8，u9 =min6，11， ， ， =6=

18、 u5 点点v5得永久标号，得永久标号， 5=2 ， X4=v1，v4 ，v3 ，v2， v5， X4=v6 ，v7，v8 ，v9， u6= 11 ，u5+w56=6+4=10， 即即 u5+w56 u6 u7= ，u5+w57=6+3=9， 即即 u5+w57 u7 u8= ，u5+w58=6+6=12， 即即 u5+w58 u8 修改临时标号修改临时标号u6= 10 ， 6=5 ， u7=9 ， 7=5 ， u8= 12 ， 8=5 ，在所有在所有vjX4中，中， K=3 +1=4 minu6，u7，u8，u9 =min10，9，12， =9= u7 点点v7得永久标号，得永久标号， 7=

19、5 ，X2=v1，v4 ，v3 ， v2， v5，v7，X2=v6 ，v8 ，v9，在在vjX5中，临时标号不变。中，临时标号不变。K=4 +1=5 minu6，u8，u9=min10，12， =10= u6 点点v6得永久标号，得永久标号， 6=5 ，X6=v1，v4 ，v3 ， v2， v5，v7 ，v6，X6=v8 ，v9，点点v8，v9临时标号不变。临时标号不变。 K=5 +1=6 minu8，u9=min12， =12= u8 点点v8得永久标号，得永久标号， 8=5 ， 即从即从v1到到v8的最短路长为的最短路长为u8=12， 8=5 ， 5=2 ， 2=3 ， 3=1 ， 知从知

20、从v1到到v8 的最短路为：的最短路为： P1，8=P（v1，v3 ， v2， v5，v8）v2v523464v3v1v4v6121061210v8v9v72363例四：如图所示，令S=a, b, f，则S=c, d, e， 求d(a, S)？ abcd125610fe1143SSDijkstra算法设u0=a，取u=a，则w(ac)=，w(ad)=10，w(ae)=，10w(av)minw(av)a)d(a,minSvSvabcd125610fe1143取取 u=b，则，则d(a,b)=6，w(bc)=5，w(bd)= w(be)=4， 1046w(bv)b)d(a,minSv取取 u=f，则，则d(a,f)=1，w(fc)=1，w(fd)=，w(fe)=2 211w(fv)f)d(a,minSv