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

1、数学建模专题练习,迪杰斯特拉算法 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=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,

2、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=2 X=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=3 X=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,1

3、0,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=3 X=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=6 X=1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1

4、,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=8 X=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=10 X=1,2,3,4,5,6,7,8, p8=10,

5、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=13 P2=（v1，v3，v4， v6， v7

6、， v8） 费用 3+2+10+2+4=21 P3= ,最短路问题中，不考虑有向环、并行弧。,最短路问题,给定有向网络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中的一个点，那么，从

7、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 的最短路长度，相应的点记“永久”标号；,

8、前点标号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

9、,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永久

10、性标号）,第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

11、 +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

12、=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