第11章通信网理论分析PPT讲稿.ppt

第11章通信网理论分析第1页，共189页，编辑于2022年，星期日11.1图图论论基基础础11.1.1网络和图网络和图1图的定义图的定义设有端集：设有端集：V=v1，v2，vn边集：边集：E=e1，e2，em当边集当边集E是端集是端集V中两个元产生关系中两个元产生关系R时，时，则则V和和E组组成成图图G，即，即G=V，E 由上述定由上述定义义可知，可知，图图G中的中的V集可任意集可任意给给定，而定，而E E集只是代表集只是代表V集中两集中两个元的关系。个元的关系。当当Vi对对Vj有某种关系有某种关系R，为邻接关系，为邻接关系er时有：时有：erE，每一个，每一个er所所对应的两个端对应的两个端Vi和和Vj称为与称为与er有关联的端，存在有关联的端，存在er的两个端称为邻接端。的两个端称为邻接端。第2页，共189页，编辑于2022年，星期日 根据端根据端间间关系的性关系的性质质，可分，可分为为有向有向图图和无向和无向图图，当，当Vi对对Vj有有某种关系等价于某种关系等价于Vj对对Vi有某种关系，就称有某种关系，就称该图为该图为无向无向图图，反之，反之则则称称为为有有向向图图。图图是集合是集合V V及其关系集及其关系集E E的的综综合合 V，E，集合，集合论论中的中的许许多概念多概念都可以移植都可以移植过过来。来。若若图图A的端集和的端集和边边集分集分别别是是图图G的端集和的端集和边边集的子集，集的子集，则图则图A是是图图G的子的子图图，表示，表示为为A G若若AG 但但AG，则则称称A是是G的真子的真子图图；若；若AG，A，则则必有必有A=G。且且G第3页，共189页，编辑于2022年，星期日2 2图的运算图的运算设设A，B为任意集合。为任意集合。AB称为称为A与与B的并集的并集（unionset），），定义为定义为AB=x|xAxB称为并运算。称为并运算。AB称为称为A A与与B B的交集的交集（intersectionset），），定义为定义为AB=x|xAxB称为交运算。称为交运算。AB称为称为A A与与B B的差集的差集（differenceset），），定义为定义为AB=x|xAx B 称为差运算。称为差运算。A称为称为A A的补集的补集（complementset），），定义为定义为A=UA=xx A 称为补运算，它是一元运算，是差运算的特例。称为补运算，它是一元运算，是差运算的特例。第4页，共189页，编辑于2022年，星期日说说明明图图的运算的示意的运算的示意图图如如图图11.1所示。所示。图图11.1图图的运算的运算第5页，共189页，编辑于2022年，星期日（1 1）并图）并图 设图设图Ga、Gb如图如图10.1（a）和（）和（b）所示，所示，Gc如图如图10.1（c）所所示。示。从图中看出，从图中看出，Gc中的端集和边集分别是中的端集和边集分别是Ga和和Gb中的端集和边集的中的端集和边集的并，称图并，称图Gc是是Ga和和Gb的并图。的并图。记为记为Gc=GaGb 对于边集和端集则有对于边集和端集则有 Vc=VaVbE=EaEb （2 2）交图）交图 Gd如图如图10.1（d）所示，则所示，则Gd是是Ga和和Gb的交图，的交图，Gb是是Ga和和Gb的公共部分，同时有的公共部分，同时有 Vd=VaVbEd=EaEb第6页，共189页，编辑于2022年，星期日（3）差）差图图 Ge如如图图10.1（e）所示，）所示，这这是从是从Ga中去掉中去掉Ga和和Gb的共有的共有边边和共有和共有端，但保留未去掉的端，但保留未去掉的边边关关联联的端。的端。Ge是是Ga和和Gb的差的差图图。记为记为Ge=GaGb（4）环环和和图图 Gf如如图图10.1（f）所示，）所示，这这是从是从GaGb中去掉中去掉Ga和和Gb的共有的共有边边。Gf是是Ga和和Gb的的环环和和图图。记为记为Gf=Ga Gb 一般来一般来说说存在存在GaGb=GaGaGb 若若GaGb=f f=空空图图，则则GaGb=Ga+Gb，称，称为为它它们们的直和。的直和。若若GbGa=GaGb，称，称为为它它们们的直差。的直差。第7页，共189页，编辑于2022年，星期日11.1.2图的矩阵表示图的矩阵表示射出射出边边射入射入边边1图的关联阵表示图的关联阵表示 关联阵是表达图的端与边的关联性的矩阵。关联阵是表达图的端与边的关联性的矩阵。若图含有若图含有m条边，条边，n个端，则图的关联阵个端，则图的关联阵A0是行数为端数，列数为是行数为端数，列数为边数的边数的nm阵，阵，A0=aijnm对于无向图则有对于无向图则有对于有向图而言，则有对于有向图而言，则有第8页，共189页，编辑于2022年，星期日 关关联联矩矩阵计阵计算用算用书书如如图图11.2所示，所示，对对于如于如图图11.2所示的有向所示的有向图图，其关，其关联联矩矩阵阵可表示可表示为为：第9页，共189页，编辑于2022年，星期日图图11.2关联矩阵计算用图关联矩阵计算用图 从从图图的关的关联联矩矩阵阵可以可以进进一步来一步来计计算算图图的生成的生成树树的数量。的数量。连连通通图图的生成的生成树树的数量可以用以下公式来表示：的数量可以用以下公式来表示：（11.1）式中式中A是是连连通通图图的关的关联联矩矩阵阵，AT是是A阵阵的的转转置。置。第10页，共189页，编辑于2022年，星期日 即此即此图图有生成有生成树树21棵。棵。以上所以上所讨论讨论的的图为图为有向有向图图，对对于无向于无向图图，可以在，可以在图图上任意上任意加箭加箭头头，得到相，得到相应应的有向的有向图图，这样这样就可求得无向就可求得无向图图的生成的生成树树的的数目。数目。以图以图11.2为例，关联阵为例，关联阵A为式（为式（11.1）所示，生成树数目可）所示，生成树数目可以由上式算得：以由上式算得：第11页，共189页，编辑于2022年，星期日2图的邻接阵的表示图的邻接阵的表示 图也可以用端与端之间的关系矩阵，即邻接阵来表示，邻接阵的图也可以用端与端之间的关系矩阵，即邻接阵来表示，邻接阵的行和列都与图的端相对应。对于一个有几个端的图，邻接阵是一个行和列都与图的端相对应。对于一个有几个端的图，邻接阵是一个nn的方阵，即的方阵，即其中其中 第12页，共189页，编辑于2022年，星期日对对于于图图11.2所示的有向所示的有向图图，其，其邻邻接接阵为阵为 （11.2）对对于无向于无向图图，则则有有 cij=eij 因此，无向因此，无向图图的的邻邻接接阵阵是一个是一个对对称称阵阵。第13页，共189页，编辑于2022年，星期日1树和生成树树和生成树树是图论中一个十分重要的概念，在网络的组播，路由选择中都有着树是图论中一个十分重要的概念，在网络的组播，路由选择中都有着广泛的应用，下面说明树的定义以及树的求法。广泛的应用，下面说明树的定义以及树的求法。树定义为一个不包括环路的连通图，它具有以下性质。树定义为一个不包括环路的连通图，它具有以下性质。树是无环的连通图，当对于任何不同的节点树是无环的连通图，当对于任何不同的节点i和和j都有一个从都有一个从i到到j的路由时，图是连通图。的路由时，图是连通图。树是最小的连通图，即树中去掉任一边就成为非连通图，树是最小的连通图，即树中去掉任一边就成为非连通图，失去了连通性，所以是最小的连通图。失去了连通性，所以是最小的连通图。若树有若树有m条边及条边及n个端，则有个端，则有m=n1这可用数学归纳法来证明。因此，树可定义为有这可用数学归纳法来证明。因此，树可定义为有n个端，个端，n1条边条边的连通图。的连通图。第14页，共189页，编辑于2022年，星期日树树的例子如的例子如图图11.3所示。所示。图图11.3树树的例子的例子 生成生成树树是是树树中的重要一中的重要一类类，下面，下面说说明它明它们们的定的定义义。设设T是是连连通通图图G的子的子图图。T G，若，若T含有含有G的所有端，的所有端，则则称称T是是G的生成的生成树树，也就是，也就是说说生成生成树树是覆盖是覆盖连连通通图图所有端的所有端的树树。只有只有连连通通图图才有生成才有生成树树，反之，有生成，反之，有生成树树的的图图必然是必然是连连通通图图。第15页，共189页，编辑于2022年，星期日对于图中的某一生成树而言，生成树上的边称为树枝，非树对于图中的某一生成树而言，生成树上的边称为树枝，非树枝的边称为连枝，生成树就是树枝集，连枝的边集称为连树集或枝的边称为连枝，生成树就是树枝集，连枝的边集称为连树集或树补。树补。在通信网的设计过程中，常涉及以下的问题：已给定一组固定的节点，在通信网的设计过程中，常涉及以下的问题：已给定一组固定的节点，在这些节点上找出一颗使全部链路的权值最小的生成树。这里的链路的权在这些节点上找出一颗使全部链路的权值最小的生成树。这里的链路的权值，可以表示各种度量值，如费用、距离、带宽、时间延迟等。值，可以表示各种度量值，如费用、距离、带宽、时间延迟等。在某些情况下，所求的树可能还受到某些约束条件的限制，如一个在某些情况下，所求的树可能还受到某些约束条件的限制，如一个典型的约束就是：必须把节点连通而使它们承载的业务量不致造成链路典型的约束就是：必须把节点连通而使它们承载的业务量不致造成链路过载。过载。求最小生成树的，需要借助于有效的算法，下面首先讨论求求最小生成树的，需要借助于有效的算法，下面首先讨论求解具有最小权但不受任何约束的一颗树的算法，然后找出有约束解具有最小权但不受任何约束的一颗树的算法，然后找出有约束条件的具有最小权的树。条件的具有最小权的树。第16页，共189页，编辑于2022年，星期日2无约束的最小生成树无约束的最小生成树（1）普列姆（）普列姆（Prim）算法）算法Prim算法具体操作是：从图中任意一个顶点开始，首先把这算法具体操作是：从图中任意一个顶点开始，首先把这个顶点包括在个顶点包括在MST里，然后在那些其一个端点已在里，然后在那些其一个端点已在MST里，另一个里，另一个端点还不是端点还不是MST里的边，找权最小的一条边，并把这条边和其不在里的边，找权最小的一条边，并把这条边和其不在MST里的那个端点包括进里的那个端点包括进MST里。如此进行下去，每次往里。如此进行下去，每次往MST里加里加一个顶点和一条权最小的边，直到把所有的顶点都包括进一个顶点和一条权最小的边，直到把所有的顶点都包括进MST里。里。假设假设V是图中顶点的集合，是图中顶点的集合，E是图中边的集合，是图中边的集合，TE为最为最小生成树中的边的集合，则小生成树中的边的集合，则prim算法的步骤如下。算法的步骤如下。第17页，共189页，编辑于2022年，星期日初始化：初始化：U=u0，TE=e0。此步骤设立一个只有节点。此步骤设立一个只有节点u0的节点集的节点集U和一个空的边集和一个空的边集TE作为最小生成树的初始状态作为最小生成树的初始状态。在所有在所有uU，vVU的边的边(u，v)E中，找一条权最小的边中，找一条权最小的边（u0，v0），将此边加进集合），将此边加进集合TE中，并将此边的非中，并将此边的非U中顶点加入中顶点加入U中。中。如果如果U=V，则算法结束；否则重复步骤，则算法结束；否则重复步骤2。可以把本步骤看成。可以把本步骤看成循环终止条件。循环终止条件。该算法的特点是当前形成的集合该算法的特点是当前形成的集合T始终是一棵树。将始终是一棵树。将T中中U和和TE分别分别看作红点和红边集，看作红点和红边集，V-U看作蓝点集，算法的每一步均是在连接红、蓝点看作蓝点集，算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进集的紫边中选择一条轻边扩充进T中。中。MST性质保证了此边是安全的。性质保证了此边是安全的。T从任意的根从任意的根r开始，并逐渐生长直至开始，并逐渐生长直至U=V，即，即T包含了包含了C中所有的顶中所有的顶点为止。点为止。MST性质确保此时的性质确保此时的T是是G的一棵的一棵MST。第18页，共189页，编辑于2022年，星期日图图11.4PRIM算法用图算法用图依依P算法可算法可顺顺序得序得d23最小最小d24最小最小d21最小最小d26最小最小d45最小最小第19页，共189页，编辑于2022年，星期日其其邻邻接接阵为阵为树树枝的枝的总长总长度度为为第20页，共189页，编辑于2022年，星期日（2）克鲁斯格尔（）克鲁斯格尔（Kruskal）算法）算法K算法每次选择算法每次选择n1条边，所使用的准则是：从剩下的边中选择一条边，所使用的准则是：从剩下的边中选择一条不会产生环路的具有最小权值的边加入已选择的边的集合中。注意条不会产生环路的具有最小权值的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。到所选取的边若产生环路则不可能形成一棵生成树。K算法分算法分e步，其步，其中中e是网络中边的数目。按权值递增的顺序来考虑这是网络中边的数目。按权值递增的顺序来考虑这e条边，每次考条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。路，则将其抛弃，否则，将它选入。假设假设W=(V，E)是一个含有是一个含有n个顶点的连通网，个顶点的连通网，K算法的步骤如下。算法的步骤如下。第21页，共189页，编辑于2022年，星期日先构造一个只含先构造一个只含n个顶点，而边集为空的子图，若将该子图个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根节点，则它是一个含有中各个顶点看成是各棵树上的根节点，则它是一个含有n棵树的一个棵树的一个森林。森林。从网的边集从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之，依此类推。取下一条权值最小的边再试之，依此类推。直至森林中只有一棵树，也即子图中含有直至森林中只有一棵树，也即子图中含有n1条边为止。条边为止。仍用仍用图图11.4来来说说明此算法。此明此算法。此时时 第22页，共189页，编辑于2022年，星期日得到：得到：形成形成环环路，路，删删去去这这条条边边。形成形成环环路，路，删删去去这这条条边边。G7就是最小生成就是最小生成树树，如，如图图案案11.4所示。所示。第23页，共189页，编辑于2022年，星期日3有约束条件的最小生成树有约束条件的最小生成树图图11.5E-W算法用图算法用图第24页，共189页，编辑于2022年，星期日 E-W算法用算法用图图如如图图11.5所示，所示，图图中中v1是中心是中心节节点，其他点，其他2、3、4、5为为端站，端站，链链路上的路上的权值为权值为dij(i，j=1，2，n)，各，各个端站的个端站的业务业务量量为为Fi(i=2，3，n)，dij的的值值示于示于图图11.5的的边边上，各个端站的上，各个端站的业务业务量示于量示于图图11.5的端的的端的边边上。上。约约束条件：要求任意一个端所到束条件：要求任意一个端所到vj的的链链路数（路数（边边数）小数）小于于k，即，即转转接次数小于接次数小于k1，边边上的上的总业务总业务量不大于量不大于M。其中其中k是是给给定的整数，而定的整数，而M是是给给定的定的实实数，本例中数，本例中设设k=3，M=50分分组组/秒秒，求符合求符合约约束条件的最小生成束条件的最小生成树树。第25页，共189页，编辑于2022年，星期日根据公式根据公式eij=dijD1i计计算的算的eij的矩的矩阵为阵为 矩矩阵阵中中e34最小，取最小，取该边该边。经经核核对满对满足足约约束条件。束条件。重新重新计计算算eij的矩的矩阵阵得得第26页，共189页，编辑于2022年，星期日 取取已有已有边边。相相连连后，后，总业务总业务量量=10+40+30=80，不符合，不符合约约束条件。束条件。，均不符合，均不符合约约束条件。束条件。，满满足足约约束条件，取束条件，取该边该边。，符合，符合约约束条件。束条件。，符合，符合约约束条件。束条件。，不符合，不符合约约束条件。束条件。取取取取取取取取取取得如图得如图11.6的解。的解。业务量如图业务量如图11.6所示，节点上的数字为该节点的业务量。所示，节点上的数字为该节点的业务量。图图11.7是无约束条件下的最小生成树，可以和有约束条件下是无约束条件下的最小生成树，可以和有约束条件下的生成树加以比较，说明约束条件在求解过程中的影响。的生成树加以比较，说明约束条件在求解过程中的影响。第27页，共189页，编辑于2022年，星期日图图11.6有约束条件下的最小生成树有约束条件下的最小生成树图图11.7无约束条件下的最小生成树无约束条件下的最小生成树第28页，共189页，编辑于2022年，星期日11.2最短路径算法最短路径算法11.2.1Bellman-Ford算法算法Bellman-Ford算法（也叫做算法（也叫做Ford-Fulkerson算法）是用以算法）是用以求解到固定点的最短路径算法。其原理是：如果某个节点在求解到固定点的最短路径算法。其原理是：如果某个节点在A和和B之间的最短路径上，则该节点到之间的最短路径上，则该节点到A的路径必定是最短路径；同样，该的路径必定是最短路径；同样，该节点到节点到B的路径也必定是最短路径。的路径也必定是最短路径。图图11.8Bellman-Ford算法用图算法用图第29页，共189页，编辑于2022年，星期日假定希望求得图假定希望求得图11.8中节点中节点2到节点到节点6（目的地）的最短路径，（目的地）的最短路径，为了到达目的地，节点为了到达目的地，节点2的分组必须首先通过节点的分组必须首先通过节点1、节点、节点4或节点或节点5中的某个节点。如果已经知道节点中的某个节点。如果已经知道节点1、节点、节点4、节点、节点5到目的地到目的地（节点（节点6）的最短路径分别是）的最短路径分别是3、3、2，这样，如果节点，这样，如果节点2的分组的分组首先通过节点首先通过节点1，则总距离（也可叫做总费用）就等于，则总距离（也可叫做总费用）就等于3+3=6；如果分组首先通过的是节点如果分组首先通过的是节点4，则总距离是，则总距离是1+3=4；如果分组首；如果分组首先通过的是节点先通过的是节点5，则总距离是，则总距离是4+2=6。因此，从节点。因此，从节点2到目的地到目的地的最短路径就是分组首先通过节点的最短路径就是分组首先通过节点4时所得到的路径。时所得到的路径。第30页，共189页，编辑于2022年，星期日为了使这种想法形式化，首先固定目的地节点，并定义为了使这种想法形式化，首先固定目的地节点，并定义Dj是节点是节点j到目的到目的地的最小费用（或最短距离）的当前预测值；地的最小费用（或最短距离）的当前预测值；Cij是节点是节点i到节点到节点j的线路费的线路费用。例如，在图用。例如，在图11.8中，中，C12=C21=2，C45=3，而从节点，而从节点i到其自身的到其自身的费用定义为费用定义为0（即（即Cii=0）。如果节点）。如果节点i到节点到节点k之间没有直接相连的线路，之间没有直接相连的线路，则它们之间的线路费用定义为无穷大。例如，在图则它们之间的线路费用定义为无穷大。例如，在图11.8中，中，C15=C23=。根据这些定义，可以求得从节点根据这些定义，可以求得从节点2到目的地节点（节点到目的地节点（节点6）的最小费用）的最小费用为为D2=minC21+D1，C24+D4，C25+D5=min3+3，1+3，4+2=4因此，节点因此，节点2到节点到节点6的最小费用为的最小费用为4，且下一个访问的节点是节点，且下一个访问的节点是节点4。第31页，共189页，编辑于2022年，星期日在计算节点在计算节点2到节点到节点6的最小费用时，假定已经知道了节点的最小费用时，假定已经知道了节点1、4、5分别到目的地的最小费用。而实际上，这些节点并没有执行同样的分别到目的地的最小费用。而实际上，这些节点并没有执行同样的计算，它们到目的地的最小费用并不是已知的，因此，为了得到这计算，它们到目的地的最小费用并不是已知的，因此，为了得到这些节点的最小费用，应用同样的原理对这些节点进行计算。例如，些节点的最小费用，应用同样的原理对这些节点进行计算。例如，D1=minC12+D2，C13+D3，C14+D4D4=minC41+D1，C42+D2，C43+D3，C45+D5可以看出，由于可以看出，由于D2依赖于依赖于D1，而，而D1又依赖于又依赖于D2，因此这些方程，因此这些方程是循环的。是循环的。只要不断地对这些方程进行迭代和更新，这个算法将收敛到正确的只要不断地对这些方程进行迭代和更新，这个算法将收敛到正确的结果。结果。第32页，共189页，编辑于2022年，星期日现现在定在定义义d是目的地是目的地节节点，点，则则可以将可以将Bellman-Ford算法算法总结总结如下：如下：初初试试化。化。D1=，idDd=0 （11.3）更新。更新。对对每个每个id 重复步重复步骤骤，直到迭代中没有新的，直到迭代中没有新的变变化出化出现现。，ji（11.4）例：利用例：利用Bellman-Ford算法，求出图算法，求出图11.8中每个节点到节点中每个节点到节点6（目的（目的地节点）的最小费用，并求出沿最短路径的下一个节点。地节点）的最小费用，并求出沿最短路径的下一个节点。现在用符号（现在用符号（n，Di）表示每个节点，这里）表示每个节点，这里n是沿当前最短路径的下是沿当前最短路径的下一个节点，一个节点，Di是节点是节点i到目的地的当前最小费用。从给出最小费用的方程到目的地的当前最小费用。从给出最小费用的方程中的中的j值可以求得下一个节点。如果下一个节点没有定义，就将值可以求得下一个节点。如果下一个节点没有定义，就将n设设置为置为1。第33页，共189页，编辑于2022年，星期日表表11.1所示为所示为Bellman-Ford算法在每次迭代结束时的结果。由于算法在每次迭代结束时的结果。由于第第3次迭代结束后不再有变化出现，因而算法在此时结束。表中的最次迭代结束后不再有变化出现，因而算法在此时结束。表中的最后一行即每个节点到节点后一行即每个节点到节点6的最短路径费用及该路径上的下一个节点。的最短路径费用及该路径上的下一个节点。表表11.1Bellman-Ford算法计算结果示例算法计算结果示例迭代节点1节点2节点3节点4节点5初始化（1，）（1，77）（1，）（1，）（1，）1（1，）（1，）（6，1）（3，3）（6，2）2（3，3）（4，4）（6，1）（3，3）（6，2）3（3，3）（4，4）（6，1）（3，3）（6，2）对于上面的例子，可以画出每个节点到目的地节点的最短路径。由表对于上面的例子，可以画出每个节点到目的地节点的最短路径。由表11.1中的最后一行可以看出，在每个节点的最短路径上，节点中的最后一行可以看出，在每个节点的最短路径上，节点1的下一个的下一个节点是节点节点是节点3；节点；节点2的下一个节点是节点的下一个节点是节点4；节点；节点3的下一个节点是节点的下一个节点是节点6，等等。，等等。第34页，共189页，编辑于2022年，星期日 Bellman-Ford算法的一个良好特性是它容易分布算法的一个良好特性是它容易分布实现实现，这样这样，每个，每个节节点点就可以独立就可以独立计计算算该节该节点到每个目的地的最小点到每个目的地的最小费费用，并将最小用，并将最小费费用矢量周期地用矢量周期地广播广播给给它的它的邻邻居居节节点。点。为为加快收加快收敛敛，路由表中的，路由表中的变变化也可用来触化也可用来触发节发节点向它点向它的的邻邻居居节节点广播最小点广播最小费费用，用，这这种技种技术术叫做触叫做触发发更新。可以更新。可以证证明，在适当的假明，在适当的假设设条件下，分布式算法也可以收条件下，分布式算法也可以收敛敛到正确的最小到正确的最小费费用上。一旦收用上。一旦收敛敛，每个，每个节节点就会知道每个目的地的最小点就会知道每个目的地的最小费费用以及最短路径上相用以及最短路径上相应应的下一个的下一个节节点。由于点。由于相相邻节邻节点之点之间间交交换换的只有的只有费费用矢量（或距离矢量），分布式用矢量（或距离矢量），分布式Bellman-Ford算算法也常常被称法也常常被称为为距离矢量算法。参与距离矢量算法的每个距离矢量算法。参与距离矢量算法的每个节节点都按下述方程点都按下述方程进进行行计计算：算：Dii=0 Dij=mink Cik+Dkj，这这里，里，Dij是是节节点点i到目的地到目的地节节点点j的最小的最小费费用。一旦更新，用。一旦更新，节节点点i就向就向它的相它的相邻节邻节点广播矢量点广播矢量Di1 Di2 Di3。分布。分布实现实现方式能方式能够够适适应线应线路路费费用用变变化或者是拓扑化或者是拓扑结结构构变变化的网化的网络络。ki第35页，共189页，编辑于2022年，星期日11.2.2Dijkstra算法算法1Dijkstra算法的原理算法的原理图图11.9Dijkstra算法用图算法用图利用图利用图11.9中所示的网作为例子来讨论中所示的网作为例子来讨论Dijkstra算法，其目的是求出源算法，其目的是求出源节点到网中所有其他节点的最短路径。在求解过程中，采取步进的方式，节点到网中所有其他节点的最短路径。在求解过程中，采取步进的方式，建立一个以源节点建立一个以源节点1为根的最短路径树，直到包括最远的节点在内为止。为根的最短路径树，直到包括最远的节点在内为止。到第到第k步，计算出到离源节点最近的步，计算出到离源节点最近的k个节点的最短路径。这些路径个节点的最短路径。这些路径定义为在集定义为在集N内。内。第36页，共189页，编辑于2022年，星期日 设设D(v)为为从源从源节节点点1到到节节点点v的距离，的距离，l(ij)为节为节点点i和和j之之间间的距离。的距离。算法分两步算法分两步执执行。行。第第1步：初始化。令步：初始化。令N=1。对对于不在于不在N中的每个中的每个节节点点v，设设置置D(v)=l(1，v)。（。（对对于与于与1不直接相不直接相连连的的节节点取点取为为）第第2步：找到一个不在步：找到一个不在N中的使中的使D(w)最小的最小的节节点点w，并将，并将w加加进进集集N中去，然后中去，然后计计算下式，以修改不在算下式，以修改不在N中的所有其他中的所有其他节节点的点的D(v)：D(v)minD(v)，D(w)+l(w，v)（11.5）重复第重复第2步直至全部步直至全部节节点包括在点包括在N中。中。表表11.2所示为求图所示为求图11.10中节点中节点1到其他节点最短路径的过程。到其他节点最短路径的过程。第37页，共189页，编辑于2022年，星期日在表中画圆圈的数字表示该步骤中在表中画圆圈的数字表示该步骤中D(w)的最小值。这样，相应的节点的最小值。这样，相应的节点w就加到就加到N中，中，D(v)的值就按要求更改。因此，在初始化后的第的值就按要求更改。因此，在初始化后的第1步，距步，距离最小离最小D(4)=w，节点，节点4就加进集合就加进集合N中；在第中；在第2步，步，D(5)=2，节，节点点5加进加进N中；如此不断继续下去。第中；如此不断继续下去。第5步以后，所有的节点都在步以后，所有的节点都在N中，中，算法终止。算法终止。表表11.2算法的计算过程算法的计算过程步骤ND（2）D（3）D（4）D（5）D（6）初始125111，424221，4，5231431，2，4，5312441，2，3，4，5212451，2，3，4，5，62312第38页，共189页，编辑于2022年，星期日图图11.10（a）中示出了以源节点）中示出了以源节点1为根的最短距离树。它的产生过为根的最短距离树。它的产生过程是：当一个节点加入集合程是：当一个节点加入集合N时，它就连接到已在时，它就连接到已在N中的适当点。每个节中的适当点。每个节点下面圆圈内的数字代表在第点下面圆圈内的数字代表在第n步该节点加入树的结构。由节点步该节点加入树的结构。由节点1的最短的最短距离树可以得到节点距离树可以得到节点1的路由选择表，如图的路由选择表，如图11.10（b）所示。该表指明）所示。该表指明了到相应的目的地节点所应选的下一节点。同理，可以求得节点了到相应的目的地节点所应选的下一节点。同理，可以求得节点2，3，6的路由选择表。的路由选择表。图图11.10节点节点1到其他节点的最短距离到其他节点的最短距离第39页，共189页，编辑于2022年，星期日2Dijkstra算法的应用算法的应用Dijkstra算法有时也被称为算法有时也被称为SPF算法，这是因为最短路径优先算算法，这是因为最短路径优先算法法SPF是是Dijkstra发明的。发明的。SPF算法是算法是OSPF路由协议的基础。该算法路由协议的基础。该算法将每一个路由器作为根（将每一个路由器作为根（root）来计算其到每一个目的地路由器的距）来计算其到每一个目的地路由器的距离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑结构离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑结构图，该结构图类似于一棵树，在图，该结构图类似于一棵树，在SPF算法中，被称为最短路径树。在算法中，被称为最短路径树。在OSPF路由协议中，最短路径树的树干长度，即路由协议中，最短路径树的树干长度，即OSPF路由器至每一路由器至每一个目的地路由器的距离，称为个目的地路由器的距离，称为OSPF的的Cost。作为一种典型的链路状态的路由协议，作为一种典型的链路状态的路由协议，OSPF还得遵循链路状态路还得遵循链路状态路由协议的统一算法。链路状态的算法非常简单，在这里将链路状态算法由协议的统一算法。链路状态的算法非常简单，在这里将链路状态算法概括为以下概括为以下4个步骤。个步骤。第40页，共189页，编辑于2022年，星期日当路由器初始化或当网络结构发生变化（例如增减路由器，当路由器初始化或当网络结构发生变化（例如增减路由器，链路状态发生变化等）时，路由器会产生链路状态广播数据包链路状态发生变化等）时，路由器会产生链路状态广播数据包（Link-StateAdvertisement，LSA），该数据包里包含路由器上所），该数据包里包含路由器上所有相连链路，即所有端口的状态信息。有相连链路，即所有端口的状态信息。更新自己的数据库，并将该链路状态信息转送给与其相邻的路由器，更新自己的数据库，并将该链路状态信息转送给与其相邻的路由器，直至系统稳定。直至系统稳定。当网络重新稳定下来，也可以说当网络重新稳定下来，也可以说OSPF路由协议收敛下来时路由协议收敛下来时，所有的路由器会根据其各自的链路状态信息数据库计算出各自的，所有的路由器会根据其各自的链路状态信息数据库计算出各自的路由表。该路由表中包含路由器到每一个可到达目的地的路由表。该路由表中包含路由器到每一个可到达目的地的Cost以以及到达该目的地所要转发的下一个路由器。及到达该目的地所要转发的下一个路由器。当网络状态比较稳定时，网络中传递的链路状态信息是比较少的，当网络状态比较稳定时，网络中传递的链路状态信息是比较少的，或者说，当网络稳定时，网络中是比较安静的。这一点实际上是或者说，当网络稳定时，网络中是比较安静的。这一点实际上是OSPF路路由协议的一个特性，这也正是链路状态路由协议区别于距离矢量路由协由协议的一个特性，这也正是链路状态路由协议区别于距离矢量路由协议的一个特点。议的一个特点。第41页，共189页，编辑于2022年，星期日11.2.3Floyd算法算法Floyd算法的基本思想是从初始距离矩阵开始，依次把网中的各节点算法的基本思想是从初始距离矩阵开始，依次把网中的各节点作为中间节点来考虑，不断地更新距离矩阵，直至矩阵中的数值收敛。作为中间节点来考虑，不断地更新距离矩阵，直至矩阵中的数值收敛。设所讨论的网中有设所讨论的网中有N个节点，个节点，S为距离矩阵，为距离矩阵，Sjk为矩阵中的元素为矩阵中的元素表示节点表示节点j与节点与节点k之间距离，之间距离，R为后续节点矩阵，为后续节点矩阵，Yjk为为R矩阵中的元素。矩阵中的元素。FIoyd算法按照下列步骤进行。算法按照下列步骤进行。初始化。对于初始化。对于j=1，2，N；k=l，2，N；置；置Sjk=d。其。其中，中，djk是节点是节点j与节点与节点k之间的直达距离。如果两个节点不直接相连，则之间的直达距离。如果两个节点不直接相连，则djk取为取为。置。置rjkk当当j=k时，时，rjk0。第42页，共189页，编辑于2022年，星期日 对对于于I=1，2，N，进进行第行第步。步。对对于于j=1，2，N；ji，进进行第行第步。步。对对于于k=1，2，N；kj，ki，进进行第行第步。步。对对Sji和和rjk进进行更新。当行更新。当Sji+SjkSjk时时，置，置SjkSji+Sik和和rjki0。算法的算法的执执行行过过程从矩程从矩阵阵S0开始，开始，等于直达距离中等于直达距离中djk，然后，然后等于从等于从j到到k的最短路径。当的最短路径。当节节点点l，2，N每次迭代均利用下式每次迭代均利用下式进进行：行：（11.6）以以I=1为中间节点，为中间节点，都是中间节点时，矩阵都是中间节点时，矩阵S(N)具有等于从具有等于从j到到k的最短路径长度的最短路径长度。第43页，共189页，编辑于2022年，星期日图图11.11Floyd算法用网算法用网 下面下面结结合具体例子合具体例子进进一步一步说说明明Floyd算法。算法。图图11.11所示所示为为一一7节节点的网，点的网，节节点之点之间间的直达距离已在的直达距离已在图图中中标标明，求此明，求此图图的最短路径的最短路径矩矩阵阵。第44页，共189页，编辑于2022年，星期日在在图图11.1的例子中，在开始的例子中，在开始时时有有 S=R=第45页，共189页，编辑于2022年，星期日 在已在已经经以以i=2完成了步完成了步骤骤2之后，也就是在已之后，也就是在已经试验过经试验过其中其中节节点点1或或2可能是中可能是中间节间节点的所有路由之后，有点的所有路由之后，有 S=R=第46页，共189页，编辑于2022年，星期日 在在这这里注意，例如，里注意，例如，S4 6=11.2，路由，路由为为（4，1）、（）、（1，2）、）、（2，6）；在前次以）；在前次以i=1通通过过步步骤骤2时时，S4 2的的值值曾以它的初曾以它的初值值（节节点点4和和2没有一个没有一个链链路加以路加以连连接）接）变变到到值值2.0，即从，即从4经过经过1到到2的路由的的路由的长长度。度。最后，在算法最后，在算法结结束束时时，得到：，得到：S=R=第47页，共189页，编辑于2022年，星期日以图以图11.11的例子可以示出使用的例子可以示出使用R矩阵来产生一个特定节点对之间最矩阵来产生一个特定节点对之间最短路由的方式。如果打算描述节点短路由的方式。如果打算描述节点2和节点和节点7之间的最短路由，从节点之间的最短路由，从节点2到到R矩阵中在全部算法完成之后由矩阵中在全部算法完成之后由r27所指示的节点，也就是进到节点所指示的节点，也就是进到节点1，且在想要的路由中第一个链路是（，且在想要的路由中第一个链路是（2，1）。然后，进到如同）。然后，进到如同r17所给出的编号的节点，也就是所给出的编号的节点，也就是3，因而继续增添，因而继续增添链路（链路（1，3）。最后，知道在最短路由从）。最后，知道在最短路由从3到到7中，中，3的后继者是的后继者是7，因而得，因而得出的路由是（出的路由是（2，1）、（）、（1，3）、（）