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

数学建模专题练习,迪杰斯特拉算法2014.09,例一、用Dijkstra算法求下图从v1到v6的最短路。,解（1）首先给v1以P标号，给其余所有点T标号。,（2）,（4）,（5）,（6）,反向追踪得v1到v6的最短路为：,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,mind12,d14,d16=min0+2,0+1,0+3=min2,1,3=1X=1,4,p4=1,p4=1,p1=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,mind12,d16,d42,d47=min0+2,0+3,1+10,1+2=min2,3,11,3=2X=1,2,4,p2=2,p1=0,p4=1,p2=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,mind16,d23,d25,d47=min0+3,2+6,2+5,1+2=min3,8,7,3=3X=1,2,4,6,p6=3,p2=2,p4=1,p1=0,p6=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,mind23,d25,c47,d67=min2+6,2+5,1+2,3+4=min8,7,3,7=3X=1,2,4,6,7,p7=3,p2=2,p4=1,p1=0,p6=3,p7=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,mind23,d25,d75,d78=min2+6,2+5,3+3,3+8=min8,7,6,11=6X=1,2,4,5,6,7,p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=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,mind23,d53,d58,d78=min2+6,6+9,6+4,3+8=min8,15,10,11=8X=1,2,3,4,5,6,7,p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=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,mind38,d58,d78=min8+6,6+4,3+7=min14,10,11=10X=1,2,3,4,5,6,7,8,p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=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。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,例三.下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。,从v1到v8：P1=（v1，v2，v5，v8）费用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用3+2+10+2+4=21P3=,最短路问题中，不考虑有向环、并行弧。,最短路问题,给定有向网络D=（V，A，W），任意弧aijA，有权w（aij）=wij，给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权（长度）是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从vs到vt的路中，求一条路P0，使,称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。,当所有wij0时，本算法是用来求给定点vs到任一个点vj最短路的公认的最好方法。,事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。,最短路的子路也是最短路。,思想：将D=（V，A，W）中vs到所有其它顶点的最短路按其路长从小到大排列为：,u0u1u2un,u0表示vs到自身的长度，相应最短路记为：,P0，P1，P2，Pn，,取最小值的点为v1，P1=P（vs，v1）,假定u0，u1，uk的值已求出，对应的最短路分别为,P1=P（vs，v1），P2=P（vs，v2），Pk=P（vs，vk）,P1一定只有一条弧。,记,则,使上式达到最小值的点v可取为vk+1。,计算过程中可采用标号方法。,Xk中的点，ui值是vs到vi的最短路长度，相应的点记“永久”标号；,前点标号i:表示点vs到vj的最短路上vj的前一点。,如i=m，表示vs到vj的最短路上vj前一点是vm。,1,6,图上标号法:,0,0,1,1,1,1,1,1,1,1,3,1,6,图上标号法:,0,0,1,1,1,1,1,1,1,1,3,1,6,0,0,1,4,11,1,1,1,1,1,1,3,图上标号法:,1,5,0,0,1,4,11,1,1,1,1,1,1,3,1,6,图上标号法:,1,5,0,0,1,4,11,1,1,1,1,1,1,3,3,5,图上标号法:,3,5,0,0,1,4,11,1,1,1,1,1,3,1,图上标号法:,3,5,0,0,1,4,11,1,1,1,1,1,3,1,图上标号法:,3,5,0,0,4,11,1,1,1,2,6,1,1,3,1,图上标号法:,3,5,0,0,4,11,1,1,1,2,6,1,1,3,1,图上标号法:,3,5,0,0,5,10,1,1,1,2,6,5,12,1,3,5,9,图上标号法:,3,5,0,0,5,10,1,1,1,2,6,5,12,1,3,5,9,图上标号法:,Dijkstra算法步骤：,第1步：令us=0，uj=wsj（1jn）若asjA，则,第3步：（给点vi永久性标号）,第4步：(修改临时标号),对所有如果,令j=i，uj=ui+wij否则,i,uj不变,把k换成k+1，返回第2步。,如果ui=+，停止，,例三.用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,K=0minu2，u3，u4，u5，u6，u7，u8，u9=min6，3，1，=1=u4,u6=，u4+w46=1+10=11，即u4+w46u6,修改临时标号u6=11，6=4，其余标号不变。,K=0+1=1minu2，u3，u5，u6，u7，u8，u9=min6，3，11，=3=u3,u2=6，u3+w32=3+2=5，即u3+w32u2,修改临时标号u2=5，2=3，其余标号不变。,k=2+1=3minu5，u6，u7，u8，u9=min6，11，=6=u5,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，,K=3+1=4minu6，u7，u8，u9=min10，9，12，=9=u7,K=4+1=5minu6，u8，u9=min10，12，=10=u6,点v8，v9临时标号不变。,K=5+1=6minu8，u9=min12，=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）,例四：如图所示，令S=a,b,f，则S=c,d,e，求d(a,S)？,Dijkstra算法,设u0=a，取u=a，则w(ac)=，w(ad)=10，w(ae)=，,取u=b，则d(a,b)=6，w(bc)=5，w(bd)=w(be)=4，,取u=f，则d(a,f)=1，w(fc)=1，w(fd)=，w(fe)=2,因而d(a,S)=2，a到S的最短路为（a,f,c）。,Dijkstra算法,Dijkstra算法,指导思想：设u0V,v0V,要求u0到v0点的距离，我们通过求u0到图中其它各点的距离。先把V分成两个子集，一个设为S,S=v|vV,u0到v的距离已求出，另一个是S=V-S。显然，S，因为至少u0S，算法不断扩大S，直到S=V(或者v0