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

数学建模专题练习,迪杰斯特拉算法 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,min d12,d14,d16=min 0+2,0+1,0+3=min 2,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,min d12,d16,d42,d47=min 0+2,0+3,1+10,1+2=min 2,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,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=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,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=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,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=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,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=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,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=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。,当所有 wij 0 时，本算法是用来求给定点vs到任一个点vj 最短路的公认的最好方法。,事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到 vi的最短路。,最短路的子路也是最短路。,思想：将D=（V，A，W）中vs到所有其它顶点的最短 路按其路长从小到大排列为：,u0 u1 u2 un,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=0 minu2，u3，u4，u5，u6，u7，u8，u9=min6，3，1，=1=u4,u6=，u4+w46=1+10=11，即 u4+w46 u6,修改临时标号u6=11，6=4，其余标号不变。,K=0+1=1 minu2，u3，u5，u6，u7，u8，u9=min6，3，11，=3=u3,u2=6，u3+w32=3+2=5，即 u3+w32 u2,修改临时标号u2=5，2=3，其余标号不变。,k=2+1=3 minu5，u6，u7，u8，u9=min6，11，=6=u5,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，,K=3+1=4 minu6，u7，u8，u9=min10，9，12，=9=u7,K=4+1=5 minu6，u8，u9=min10，12，=10=u6,点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，,知从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算法,指导思想：设u0 V,v0 V,要求u0到v0点的距离，我们通过求u0到图中其它各点的距离。先把V分成两个子集，一个设为S,S=v|v V,u0到v的距离已求出，另一个是S=V-S。显然，S，因为至少u0S，算法不断扩大S，直到S=V(或者v0 S)对任意的v S=V-u0，设l(v)表示从u0仅经过S中的点到v的最短路的带权长度。若不存在这样的路，置l(v)=。,Dijkstra算法,(1)初始化，令S=u0，S=V-S，对 S中每一个点v,令l(v)=w(u0,v)；,(2)找到uiS，满足,(3)若S=V，则终止；否则令S=Sui，S=S-ui,对 S中每一个点v，计算,转到(2)。,Dijkstra算法,执行过程:,