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

数学建模专题练习 迪杰斯特拉算法 2014.09例一、例一、 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路的最短路 v1v2v3v4v6v5352242421 解解 （1）首先给v1以P标号，给其余所有点T标号2） v1v2v3v4v6v5352242421（4）v1v2v3v4v6v5352242421（5）（6）反向追踪得v1到v6的最短路为：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=0237184566134105275934682X={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=2237184566134105275934682X={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=3237184566134105275934682X={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=3237184566134105275934682X={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=6237184566134105275934682X={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=8237184566134105275934682X={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=10237184566134105275934682X={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 ，使，使 称称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，，取最小值的点为取最小值的点为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 的最短路长度，相应的最短路长度，相应的点记的点记“永久永久”标号；标号； 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,31,6图上标号法图上标号法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01, ∞ 1, ∞1,11, ∞1, ∞1, ∞ 1,31,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 1210v8v9v72363v60,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 1210v8v9v72363v60,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 （（1≤j≤n）若）若asj A，则，则第第2步：步：(选永久标号选永久标号)在在XK中选一点中选一点vi，满足，满足 第第3步：（给点步：（给点vi永久性标号）永久性标号） 第第4步：步：(修改临时标号修改临时标号)对所有对所有 如果如果 令令  j=i，，uj=ui+wij否则否则,  i,,uj 不变不变,把把k换成换成k+1，返回第，返回第2步。

步如果如果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}v2v523464v3v1v4v6121061210v8v9v72363K=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+w46< u6 ∴∴ 修改临时标号修改临时标号u6= 11 ，， 6=4 ，其余标号不变。

其余标号不变v2v523464v3v1v4v6121061210v8v9v72363K=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+w32< u2 ∴ 修改临时标号修改临时标号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+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 ，，在所有在所有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例四：如图所示，令S={a, b, f}，则S’={c, d, e}， 求d(a, S’)？ abcd125610fe1143S’SDijkstra算法设u0=a，取u=a，则w(ac)=∞，w(ad)=10，w(ae)=∞，abcd125610fe1143取取 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 abcd125610fe1143因而因而d(a, S’)=2，，a到到S’的最短路为的最短路为（（a, f, c）。

Dijkstra算法Dijkstra算法指导思想：设u0 V, v0 V ,要求u0到v0点的距离，我们通过求u0到图中其它各点的距离先把V分成两个子集，l一个设为S, S={v|v V, u0到v的距离已求出}，l另一个是S’= V -Sl显然，S，因为至少u0S，算法不断扩大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)找到找到ui S’，满足，满足(3) 若若S= V ，则终止；否则令，则终止；否则令S=S∪∪{ui}，， S’=S’-{ui},对对 S’中每一个点中每一个点v，计算，计算转到转到(2)(2)Dijkstra算法bacd762fe81443472356321u0gl(g)l(f)l(e)l(d)l(c)l(b)l(a)S’S712∞∞∞∞48abcdefgu01724∞∞48abcdegu0 f273∞∞48abcdgu0 fe36948abcgu0 fed4696acgu0 fedb569cgu0 fedba69cu0 fedbag7u0 fedbagc8bacd762fe81443472356321u0g执行过程执行过程:。