第五部分图论第二部分教学课件.ppt
《第五部分图论第二部分教学课件.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的各边权之和。 这与
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 部分 第二 教学 课件
链接地址:https://www.31doc.com/p-3124120.html