《第五部分图论第二部分教学课件.ppt》由会员分享，可在线阅读，更多相关《第五部分图论第二部分教学课件.ppt（39页珍藏版）》请在三一文库上搜索。
1、1,第 五 章 图 论 (第二部分),1. 通路 2. 图的连通性 3. 赋权图的最短通路,2,赋权图与边的权,定义权 在图的点或者边上标明的信息(数量)称为权。 边e的权记为W(e)； 如果用两个端点的序列(u, v)表示边，则边(u,v)的权记为W(u,v) 。 规定： (1) W(uu) = 0， 若(u, u) E(G), (2) W(uv) = , 若(u, v) E(G)。 定义赋权图 顶点或边含有权的图称为赋权图。赋权图可以是有向图或者无向图。,3,例: 赋权图边权值例,W(a,b)=5， W(a,a)=0， W(b,d)=， W(a,d)=8,4,最短通路,定义最短通路 在一个
2、边赋权的图G中，从u到v的所有通路中，边权值和最小的通路，称为u到v的最短通路（最短路径），最短通路的边权和称为u到v的距离。 两点间的最短通路必为基本通路。,5,最短通路例,A,F,B,C,D,E,6,枚举法求最短通路,求a到c的最短通路 a到c的基本通路有： (a, b, c)边权和为5+4=9; (a, c)边权和为12; (a, d, c)边权和为8+20= 28。 最短路为： abc，因此a到c的距离为9,7,狄克斯特洛(Dijkstra)算法,求图G=(V,E)中从结点a到结点z的最短通路。 基本思想动态规划法 (1) 求出以a为起点，V-a中的点为终点的最小最短通路P1；设P1终
3、点为t1; 若t1 = z，则P1为a到z的最短通路； 否则，执行(2) (2) 求出以a为起点， V-a,t1中的点为终点的最小最短通路P2；设P2终点为t2； 若t2 = z，则P2为a到z的最短通路； 否则，执行(3) (3) 求出以a为起点，V-a,t1,t2中的点为终点的最小最短通路P3；设P3终点为t3； 若t3= z，则P3为a到z的最短通路； 否则，执行(4) (4) 依此类推，直到求得的第k条最短通路Pk；终点为z。,8,狄克斯特洛算法：相关定义,设G=(V, E)，求G中a到z的最短通路。 定义目标集 目标集T是满足以下条件的集合： (1) T V (2) z T, z是最
4、短通路的终点 (3) a T, a是最短通路的起点 定义指标 设t1 T，由a到t1但不通过目标集T中其它顶点的所有通路中，各边的权之和的最小者，称为t1关于目标集T的指标，记作DT(t1).,设T=c, e, f, g, z, 求DT(c). a到c但不通过目标集T中其它顶点的所有基本通路: (a, b, c): 各边权之和: 1+2 = 3 (a, c): 各边权之和: 4 (a, d, c): 各边权之和: 4+3 = 7, DT(c) = 3,T,G,9,狄克斯特洛算法：原理,原理: 设目标集T = t1, t2, , tn, 其中t1为T中指标最小的点，即： DT(t1) = min
5、DT(t1), DT(t2) , , DT(tn) (1) 始点a到t1的最短通路的边权和就是DT(t1) (2) 对任意2 in， a到t1的最短通路 a到ti的最短通路,设T = e, f, g, z, 已求得 DT( e ) = 9; DT( f ) = 6; DT( g ) = 8; DT( z ) = ; 在T的所有结点中，a到f的最短通路最小 并且a到f的最短通路的边权值和为DT(f)=6。,G,10,狄克斯特洛算法：原理证明（1）,证明： (1) (反证法) 假设a到t1的最短通路的权和不是DT(t1). 已知DT(t1)是从a到t1但不通过T中其它顶点的通路中权和最小者，所以如
6、果存在另一条权和小于DT(t1)的新通路，则该通路一定至少通过T中一个其它顶点。,11,狄克斯特洛算法：原理证明（2）,证明(续)： 设新通路的边权和为dnew，则 dnew DT(t1) 其中w(t2t1) 表示新通路中t2到t1的各边权之和。 这与“dnew DT(t1)”矛盾。 a到t1的最短通路的权和只能是DT(t1).,a,T,t1,t2,12,狄克斯特洛算法：原理证明（2）,证明(续)： (2) (反证法) 假设存在ti(i2) ，使得a到ti的最短通路小于a到t1的最短通路。设该通路为P，边权值和为d。则d DT(t1) 其中w(t2t1) 表示P中t2到ti的各边权之和。 这与
7、“d DT(t1)”矛盾。 (2)得证。,a,T,ti,t2,13,狄克斯特洛算法,求图G=(V, E)中a到z的最短通路。 步骤： （1）令初始目标集T1V-a。求T1中指标最小的结点，设为t1。 若t1=z，则DT1(t1)为a到z的最短通路边权和。 否则，执行（2） （2）令T2=T1-t1,求T2中指标最小的结点，设为t2。 若t2=z,则DT2(t2)为a到z最短通路边权和。 否则，执行(3) （3） 依此类推，直到求得某个目标集Tk，使得z为Tk中指标最小的结 点，则DTk(z)为a到z的最短通路的边权和。 关键：求结点关于目标集Ti的指标。,14,采用“递推”的方法求目标集中的指
8、标,已知当前目标集为Tm=tm, tm+1, , tn，且 DTm(ti)是ti关于目标集T的指标，tm是最小指标点。 要求新的目标集Tm+1= Tm tm中任意点ti的指标 可用下公式求得：,tm,tn,tm+1,tm,Tm,Tm+1,注： 当tm与ti不邻接时，W(tm,ti),15,狄克斯特洛算法：执行步骤,求图G=(V, E)中a到z的最短通路。 算法执行步骤： (1) 将目标集设置为：T = V a (2) 对任意vT，令DT(v)=W(a,v)； (3) 将T中指标值最小的点t从T中剔除，即令TTt； 。 (4) 若t = z，则DT(z)为a到z的最短路径权值，算法结束。 否则（
9、即t z） ，执行以下操作： 对所有v T，令DT(v)=min(DT(v), DT(t)+W(t,v)； 重复(3). 算法执行结束后，DT(z)就是从a到z的最短通路的权和。,16,狄克斯特洛算法求最短通路举例,例：求下图中从始点a到终点z的最短通路。,17,首先，取初始目标集T1b,c,d,e,f,g,z。 易见: DT1(b) = 1 （通路：ab） DT1(c) = 4 （通路：ac） DT1(d) = 4 （通路：ad） DT1(e) = DT1(f) = DT1(g) = DT1(z)= （无通路）,T1,比较各点的指标可知，b是最小的指标点，b的指标对应的通路为ab。,18,c
10、是指标最小的点。,T2,通路：abc,通路：ad,通路：abe,通路：无,通路：无,通路：无,a到c的最短通路为：abc,边权和为DT2(c)=3,DT1(b) = 1 （通路：ab） DT1(c) = 4 （通路：ac） DT1(d) = 4 （通路：ad） DT1(e) = DT1(f) = DT1(g) = DT1(z)= （无通路）,19,通路：ad,通路：abce,通路：abcf,通路：abcg,通路：无,比较T3中各点指标可知：d的指标最小，故DT3(d)=4是a到d的最短路径长度，ad是a到d的最短路径,T3,20,令 T4T3d=e, f, g, z T4中各结点的指标为：,通
11、路：abce,通路：abcf,通路：abcg,通路：无,比较T4中各点指标可知：f的指标最小，故DT4(f)=6是a到f的最短路径长度，abcf是a到f的最短路径。,T4,21,比较T4中各点指标可知：e和g的指标相同，且最小，故可选其中一个，DT5(e)=8是a到e的最短路径长度，abcfe是a到e的最短路径。,令 T5T4f=e, g, z T5中各结点的指标为：,通路：abcfe,T5,通路：abcg,通路：abcg,22,令 T6T5e=g, z T6中各结点的指标为：,T6,比较T6中各点指标可知：f的指标最小，故DT6(g)=6是a到g的最短路径长度，abcg是a到g的最短路径。,
12、通路：abcg,通路：abcfez,23,令 T7T6g=z T7中各结点的指标为：,故a到z的最短通路边权和为DT7(z)=9， 通路为abcfez,通路：abcfez,T7,24,求最短通路的表格表示法,步骤：,(1) 先把T1=V a中各点写在第一行上，把各点的指标写在第二行上 然后圈出其中最小指标点。,1,T1,25,(2) 在第三行上，相应地写上T2=T1b中各点的指 标。在求T2中点t的指标时，利用公式,求出T2中各点的指标后，圈出最小指标点。,3,T2,T1,T1,26,在第四行上，相应地写上T3=T2 c 中各点的指标。,利用公式：,求出T3的指标以后，圈出其中最小指标的点。,
13、4,T2,T1,T3,27,采用同样的方法，可得完整的表格如下：,28,逆向检查法，找最短通路,29,ez fez cfez bcfez 所以最短通路为：abcfez,30,例：采用表格表示法求下图中a点到z点的最短路径,3,31,5,6,1,T1,3,表格求解步骤（1）,32,表格求解步骤（2）,6,9,4,T2,3,T1,33,表格求解步骤（3）,6,9,8,7,T2,3,T1,T3,34,表格求解步骤（4）,9,8,11,7,T3,3,T2,T4,35,表格求解步骤（5）,9,8,9,13,T4,3,T3,T5,36,求解过程表格表示如下：,用逆向检查法，可得最短通路为: abcghz,T1,T2,T3,T4,T5,T6,T7,T8,37,课堂练习,求u0到c的最短路径,38,Dijkstra算法执行过程,路径： u0，e，d，c,39,作业,P203：3、5,