第 五 章 图 论 (第二部分)1. 通路通路2. 图的图的连通性连通性3. 赋权图的最短通路赋权图的最短通路1赋权图与边的权赋权图与边的权 定义定义权权 在图的点或者边上标明的信息在图的点或者边上标明的信息(数量数量)称为称为权。权。l边边e的权记为的权记为W(e)； 如果用两个端点的序列如果用两个端点的序列(u, v)表示边，则边表示边，则边(u,v)的权记为的权记为W(u,v) 。l规定：规定： (1) W(uu) = 0， 若若(u, u) E(G), (2) W(uv) = , 若若(u, v) E(G)。 定义定义赋权图赋权图 顶点或边含有权的图称为顶点或边含有权的图称为赋权图赋权图。赋权图可以是。赋权图可以是有向图有向图或者或者无向图。无向图。2例例: 赋权图边权值例赋权图边权值例 W(a,b)=5，W(a,a)=0，W(b,d)=，W(a,d)=8 abcd51248203最短通路最短通路 定义定义 最短通路最短通路l在一个边赋权的图在一个边赋权的图G中，从中，从u到到v的所有通路中，的所有通路中，边边权值和最小的通路，称为权值和最小的通路，称为u到到v的的最短通路（最最短通路（最短路径），短路径），最短通路的边权和称为最短通路的边权和称为u到到v的距离的距离。 l两点间的最短通路必为两点间的最短通路必为基本通路基本通路。 4最短通路例最短通路例515217420268AFBCDE5枚举法求最短通路枚举法求最短通路 求求a到到c的最短通路的最短通路a到到c的基本通路有：的基本通路有：(1)(a, b, c)边权和为边权和为5+4=9;(2)(a, c)边权和为边权和为12;(3)(a, d, c)边权和为边权和为8+20= 28。最短路为：最短路为： abc，因此因此a到到c的距离为的距离为9abcd51248206狄克斯特洛狄克斯特洛(Dijkstra)算法算法l求图求图G=(V,E)中从结点中从结点a到结点到结点z的最短通路。的最短通路。 l基本思想动态规划法基本思想动态规划法 (1) 求出以求出以a为起点，为起点，V-a中的点为终点的最小最短通路中的点为终点的最小最短通路P1；设；设P1终点为终点为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。7狄克斯特洛算法：狄克斯特洛算法：相关定义相关定义设设G=(V, E)G=(V, E)，求，求G G中中a a到到z z的最短通路。的最短通路。 定义定义 目标集目标集目标集目标集T T是满足以下条件的集合：是满足以下条件的集合：(1) T (1) T V V(2) z (2) z T, z T, z是最短通路的终点是最短通路的终点(3) a (3) a T, a T, a是最短通路的起点是最短通路的起点 定义定义 指标指标 设设t t1 1 T T，由，由a a到到t t1 1但不通过目标但不通过目标集集T T中其它顶点的中其它顶点的所有通路所有通路中，各边中，各边的权之和的最小者，称为的权之和的最小者，称为t t1 1关于目标关于目标集集T T的指标的指标，记作，记作DT(tDT(t1 1).).设设T=c, e, f, g, z, T=c, e, f, g, z, 求求DT(cDT(c).).a a a a到到到到c c c c但不通过目标集但不通过目标集但不通过目标集但不通过目标集T T T T中其它顶点的中其它顶点的中其它顶点的中其它顶点的所有基本通路所有基本通路所有基本通路所有基本通路: : : :(a, b, c): (a, b, c): (a, b, c): (a, b, c): 各边权之和各边权之和各边权之和各边权之和: 1+2 =: 1+2 =: 1+2 =: 1+2 = 3 3 3 3(a, c): (a, c): (a, c): (a, c): 各边权之和各边权之和各边权之和各边权之和: 4: 4: 4: 4(a, d, c): (a, d, c): (a, d, c): (a, d, c): 各边权之和各边权之和各边权之和各边权之和: 4+3 = 7: 4+3 = 7: 4+3 = 7: 4+3 = 7 DT(c) = 3badecfgz1442396357143TG8狄克斯特洛算法：狄克斯特洛算法：原理原理原理原理: 设目标集设目标集T = t1, t2, , tn, 其中其中t1为为T中指标最中指标最小的点小的点，即：，即：DT(t1) = minDT(t1), DT(t2) , , DT(tn) (1) 始点始点a到到t1的最短通路的边权和就是的最短通路的边权和就是DT(t1) (2) 对任意对任意2 i n， a到到t1的最短通路的最短通路 a到到ti的最短通的最短通路路设设设设T = e, f, g, z, T = e, f, g, z, 已求得已求得已求得已求得DT( e ) = DT( e ) = 9 9; DT( f ) = ; DT( f ) = 6 6; ;DT( g ) = DT( g ) = 8 8; DT( z ) = ; DT( z ) = ; ; 在在在在T T的所有结点中，的所有结点中，的所有结点中，的所有结点中，a a到到到到f f的最的最的最的最短通路最小短通路最小短通路最小短通路最小 并并并并且且且且a a到到到到f f的最短通路的边权值的最短通路的边权值的最短通路的边权值的最短通路的边权值和为和为和为和为DT(fDT(f)=6)=6。badecfgz1442396357143TG9狄克斯特洛算法：狄克斯特洛算法：原理证明（原理证明（1） l证明：证明： (1) (反证法反证法) 假设假设a到到t1的最短通路的权和的最短通路的权和不不是是DT(t1). 已知已知DT(t1)是是从从a a到到t t1 1但不通过但不通过T T中其它顶中其它顶点的通路中权和最小者点的通路中权和最小者，所以如果存在另一条，所以如果存在另一条权和小于权和小于DT(t1)的的新通路新通路，则该通路一定，则该通路一定至少至少通过通过T T中一个其它顶点中一个其它顶点。10狄克斯特洛算法：狄克斯特洛算法：原理证明（原理证明（2）l证明证明(续续)： 设新通路的边权和为设新通路的边权和为dnew，则，则 dnew DT(t1) 其中其中w(t2t1) 表示新通路中表示新通路中t2到到t1的的各边权之和。各边权之和。 这与这与“dnew DT(t1)”矛盾矛盾。 a到到t1的最短通路的权和只能是的最短通路的权和只能是DT(t1).aTt1t211狄克斯特洛算法：狄克斯特洛算法：原理证明（原理证明（2）l证明证明(续续)： (2) (反证法反证法) 假设存在假设存在ti(i 2) ，使，使得得a到到ti的最短通路小于的最短通路小于a到到t1的最短通的最短通路。设该通路为路。设该通路为P，边权值和为，边权值和为d。则。则dDT(t1)且且d DT(t1) 其中其中w(t2t1) 表示表示P中中t2到到ti的各边权的各边权之和。之和。 这与这与“d DT(t1)”矛盾矛盾。 (2)得证。得证。aTtit212狄克斯特洛算法狄克斯特洛算法l求图求图G=(V, E)G=(V, E)中中a a到到z z的最短通路。的最短通路。 步骤：步骤： （1 1）令初始目标集）令初始目标集T T1 1V-aV-a。求。求T T1 1中指标最小的结点，设为中指标最小的结点，设为t t1 1。 若若t t1 1=z=z，则，则DTDT1 1(t(t1 1) )为为a a到到z z的最短通路边权和。的最短通路边权和。 否则，执行（否则，执行（2 2） （2 2）令）令T T2 2=T=T1 1-t-t1 1,求求T T2 2中指标最小的结点，设为中指标最小的结点，设为t t2 2。 若若t t2 2=z,=z,则则DTDT2 2(t(t2 2) )为为a a到到z z最短通路边权和。最短通路边权和。 否则，执行否则，执行(3)(3) （3 3） 依此类推，直到求得某个目标集依此类推，直到求得某个目标集T Tk k，使得，使得z z为为T Tk k中指标最小的结中指标最小的结 点，则点，则DTDTk k(z(z) )为为a a到到z z的最短通路的边权和。的最短通路的边权和。关键关键：求结点关于目标集：求结点关于目标集T Ti i的指标。的指标。13采用采用“递推递推”的方法求目标集中的指标的方法求目标集中的指标 已知当前目标集为已知当前目标集为Tm=tm, tm+1, , tn，且，且DTm(ti)是是ti关于目标集关于目标集T的指标，的指标，tm是最小指标点。是最小指标点。 要求新的目标集要求新的目标集Tm+1= Tm tm中任意点中任意点ti的指标的指标 可用下公式求得：可用下公式求得： tmtntm+1tmTmTm+1tm-1t2t1a注：注：1.1.当当t tm m与与t ti i不邻接时，不邻接时，W W( (t tm m,t,ti i) )14狄克斯特洛算法：狄克斯特洛算法：执行步骤执行步骤求图求图G=(V, E)G=(V, E)中中a a到到z z的最短通路。的最短通路。算法算法执行步骤：执行步骤：(1) 将目标集设置为：将目标集设置为：T = V a(2) 对任意对任意v T，令，令DT(v)=W(a,v)； (3) 将将T中指标值最小的点中指标值最小的点t从从T中剔除，即令中剔除，即令TTt； 。(4) 若若t = z，则，则DT(z)为为a到到z的最短路径权值，算法结束。的最短路径权值，算法结束。 否则（即否则（即t z） ，执行以下操作：，执行以下操作： 对所有对所有v T，令，令DT(v)=min(DT(v), DT(t)+W(t,v)； 重复重复(3).l算法执行结束后，算法执行结束后，DT(z)就是从就是从a到到z的最短通路的权和。的最短通路的权和。15狄克斯特洛算法求最短通路举例狄克斯特洛算法求最短通路举例例：求下图中从始点例：求下图中从始点例：求下图中从始点例：求下图中从始点a a到终点到终点到终点到终点z z的最短通路。的最短通路。的最短通路。的最短通路。16首先，取初始目标集首先，取初始目标集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是最小的指标是最小的指标点，点，b b的指标对应的的指标对应的通路为通路为abab。17c c是指标最小的点。是指标最小的点。T2通路通路：abc通路：通路：ad通路通路：abe通路通路：无无通路：无通路：无通路：无通路：无a a到到c 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)= （无通路）（无通路）18通路通路：ad通路通路：abce通路通路：abcf通路通路：abcg通路：无通路：无比较T3中各点指标可知：d的指标最小，故DTDT3 3(d)(d)=4是a到d的最短路径长度，adad是a到d的最短路径T319令 T4T3d=e, f, g, zT4中各结点的指标为： 通路通路：abce通路通路：abcf通路通路：abcg通路通路：无无比较T4中各点指标可知：f的指标最小，故DTDT4 4(f)(f)=6是a到f的最短路径长度，abcfabcf是a到f的最短路径。T420比较T4中各点指标可知：e和g的指标相同，且最小，故可选其中一个，DTDT5 5(e)(e)=8是a到e的最短路径长度，abcfeabcfe是a到e的最短路径。令 T5T4f=e, g, z T5中各结点的指标为：中各结点的指标为： 通路通路：abcfeT5通路通路：abcg通路通路：abcg21令 T6T5e=g, z T6中各结点的指标为：中各结点的指标为： T6比较T6中各点指标可知：f的指标最小，故DTDT6 6(g)(g)=6是a到g的最短路径长度，abcgabcg是a到g的最短路径。通路通路：abcg通路通路：abcfez22令 T7T6g=z T7中各结点的指标为：中各结点的指标为： 故a到z的最短通路边权和为DT7(z)=9， 通路为abcfez通路通路：abcfezT723求最短通路的表格表示法求最短通路的表格表示法步骤：步骤： (1) 先把先把T1=V a中各点写在第一行上，把各点的中各点写在第一行上，把各点的指标写在第二行上指标写在第二行上 然后圈出其中最小指标点。然后圈出其中最小指标点。b bc cd de ef fg gz z4 44 41T124b bc cd de ef fg gz z4 44 4 (2) 在第三行上，相应地写上在第三行上，相应地写上T2=T1b中各点的指中各点的指 标。在求标。在求T2中点中点t的指标时，利用公式的指标时，利用公式 求出求出T2中各点的指标后，圈出最小指标点。中各点的指标后，圈出最小指标点。b bc cd de ef fg gz z4 44 44 410103T2T1T125在第四行上，相应地写上在第四行上，相应地写上T3=T2 c 中各点的指标。中各点的指标。利用公式：利用公式：求出求出T3的指标以后，圈出其中最小指标的点。的指标以后，圈出其中最小指标的点。b bc cd de ef fg gz z4 44 44 410109 96 68 84T2T1T326采用同样的方法，可得完整的表格如下：采用同样的方法，可得完整的表格如下：b bc cd de ef fg gz z4 44 44 410109 96 68 89 98 88 810109 9T1T2T3T4T5T6T727逆向检查法，找最短通路逆向检查法，找最短通路28b bc cd de ef fg gz z4 44 44 410109 96 68 89 98 88 810109 9e ez zf fe ez zc cf fe ez zb bc cf fe ez z所以最短通路为：所以最短通路为：所以最短通路为：所以最短通路为：a ab bc cf fe ez zT1T2T3T4T5T6T729例：采用表格表示法求下图中例：采用表格表示法求下图中a点到点到z点的最短路径点的最短路径330bcdefghz561T13表格求解步骤（表格求解步骤（1）31表格求解步骤（表格求解步骤（2）694T23bcdefghz56T132表格求解步骤（表格求解步骤（3）6987T23bcdefghz5669T1T333表格求解步骤（表格求解步骤（4）98117T33bcdefghz69987T2T434表格求解步骤（表格求解步骤（5）98913T43bcdefghz9879811T3T535bcdefghz56699879811991391212求解过程表格表示如下：求解过程表格表示如下：用逆向检查法，可得最短通路为用逆向检查法，可得最短通路为: : a ab bc cg gh hz zT1T2T3T4T5T6T7T836课堂练习课堂练习l求求u0到到c的最短路径的最短路径bacd762fe81443472356321u0g37Dijkstra算法执行过程算法执行过程gfedcbaTS7 248abcdefgu017 448abcdegu0 f27 48abcdgu0 fe369 8abcgu0 fed469 acgu0 fedb5 9cgu0 fedba6 cu0 fedbag7u0 fedbagc8l路径： u0，e，d，c38作业作业lP203：3、539