《第五章图论（第二部分）》由会员分享，可在线阅读，更多相关《第五章图论（第二部分）（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) = minDT(t1), DT(t2) , , DT(tn) (1) 始点a到t1的最短通路的边权和就是DT(t1) (2) 对任意2 in， a到t1的最短通路 a到ti的最短通路,
