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

数学建模专题练习迪杰斯特拉算法2014.09例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先给v1以P标号，给其余所有点T标号。0)(1vP)6,,3,2()(ivTi（2）3]30,min[])(,)(min[)(12122lvPvTvT5]50,min[])(,)(min[)(13133lvPvTvT3)(,3)()}(),(),(),(),(min{)}({min2265432vpvTvTvTvTvTvTvTjsvj所以有，v1v2v3v4v6v5352242421（4）4]13,5min[])(,)(min[)(23233lvPvTvT5]23,min[])(,)(min[)(24244lvPvTvT5]23,min[])(,)(min[)(25255lvPvTvT4)(,4)()}(),(),(),(min{)}({min336543vpvTvTvTvTvTvTjsvj所以有，v1v2v3v4v6v5352242421（5）5]44,5min[])(,)(min[)(35355lvPvTvT7]25,45,min[])(,)(,)(min[)(56546466lvPlvPvTvT（6）反向追踪得v1到v6的最短路为：6521vvvv5)(,5)(,5)()()}(),(),(min{)}({min5454654vpvpvTvTvTvTvTvTjsvj所以有，7)(,7)}(min{)}({min66vpvTvTjsvj所以有，237184566134105275934682例二.求从1到8的最短路径237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{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=2237184566134105275934682X={1,2,4}min{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,6}min{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,7}min{d23,d25,d75,d78}=min{2+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,7}min{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,7}min{d38,d58,d78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10例三.下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从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），任意弧aij∈A，有权w（aij）=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最短路的公认的最好方法。事实：如果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,X\VXX则记取最小值的点为v1，∴P1=P（vs，v1）假定u0，u1，…，uk的值已求出，对应的最短路分别为P1=P（vs，v1），P2=P（vs，v2），…，Pk=P（vs，vk）P1一定只有一条弧。记kkkskvvvvX\VX,,...,,,X21则)',w(miniX'X1vvuuivvkkki使上式达到最小值的点v’可取为vk+1。计算过程中可采用标号方法。Xk中的点，ui值是vs到vi的最短路长度，相应的点记“永久”标号；XK中的点，ui值是vs到vi的最短路长度的上界，相应的点记“临时”标号，供进一步计算使用。前点标号i:表示点vs到vj的最短路上vj的前一点。如i=m，表示vs到vj的最短路上vj前一点是vm。1,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,3图上标号法:1,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,6图上标号法:1,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,33,5图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,9图上标号法:3,5v5v223464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,9图上标号法:Dijkstra算法步骤：第1步：令us=0，uj=wsj（1≤j≤n）若asjA，则第2步：(选永久标号)在XK中选一点vi，满足第3步：（给点vi永久性标号）第4步：(修改临时标号)对所有如果,Xv1kjjijiuwu令j=i，uj=ui+wij否则,i,,uj不变,把k换成k+1，返回第2步。jXviuminuKj如果ui=+，停止，令Xk+1=Xk∪﹛vi﹜,Xk+1=Xk＼﹛vi﹜令wsj=+,X0={vs},X0=V\X0,k=0,i=0(0≤j≤n）从vs到XK中各点没有路；否则，转第3步。如果Xk+1=，结束，到所有的点的最短路已经求得；否则，转第4步。例三.用Dijkstra算法求前面例子中从v1到各点的最短路。解：u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+，j=1（j=2，3，…，9）X0={v1}，X0={v2，v3，…，v9}v2v523464v3v1v4v6121061210v8v9v72363K=0∵min{u2，u3，u4，u5，u6，u7，u8，u9}=min{6，3，1，，，，，}=1=u4∴点v4得永久标号，4=1，X1={v1，v4}，X1={v2，v3，v5，v6，v7，v8，v9}，在所有vj∈X1中，∵u6=，u4+w46=1+10=11，即u4+w46u6∴修改临时标号u6=11，6=4，其余标号不变。v2v523464v3v1v4v6121061210v8v9v72363K=0+1=1∵min{u2，u3，u5，u6，u7，u8，u9}=min{6，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+w32u2∴修改临时标号u2=5，2=3，其余标号不变。在所有vj∈X2中，k=2+1=3∵min{u5，u6，u7，u8，u9}=min{6，11，，，}=6=u5∴点v5得永久标号，5=2，X4={v1，v4，v3，v2，v5}，X4={v6，v7，v8，v9}，∵u6=11，u5+w56=6+4=10，即u5+w56u6u7=，u5+w57=6+3=9，即u5+w57u7u8=，u5+w58=6+6=12，即u5+w58u8∴修改临时标号u6=10，6=5，u7=9，7=5，u8=12，8=5，在所有vj∈X4中，K=3+1=4∵min{u6，u7，u8，u9}=min{10，9，12，}=9=u7∴点v7得永久标号，7=5，X2={v1，v4，v3，v2，v5，v7}，X2={v6，v8，v9}，在vj∈X5中，临时标号不变。K=4+1=5∵min{u6，u8，u9}=min{10，12，}=10=u6∴点v6得永久标号，6=5，X6={v1，v4，v3，v2，v5，v7，v6}，X6={v8，v9}，点v8，v9临时标号不变。K=5+1=6∵min{u8，u9}=min{12，}=12=u8∴点v8得永久标号，8=5，即从v1到v8的最短路长为u8=12，∵8=5，5=2，2=3，3=1，知从v1到v8的最短路为：P1，8=P（v1，v3，v2，v5，v8）v2v523464v3v1v4v6121061210v8v9v72363例四：如图所示，