第二章 通信网的拓扑结构bqip.docx

第2章 通信网拓扑结构第二章 通信网网拓扑结结构 通信网网的拓扑扑结构是是很基本本，也是是很重要要的问题题。拓扑扑结构是是通信网网规划和和设计的的第一层层次问题题。通信信网的拓拓扑结构构可以用用图论的的模型来来代表，主主要的问问题为最最短径和和网络流流量问题题。本章章还介绍绍了线性性规划问问题的基基本概念念和方法法及网络络优化结结构模型型。§2.11图论基基础图论是应应用数学学的一个个分支，本本节介绍绍它的一一些概念念和结论论。其基基本内容容可参见见（1）和和（2）。2.1.1图的的定义 例2.11 哥尼尼斯堡77桥问题题;所谓一个个图，是是指给了了一个集集合V，以及及V中元素素的序对对集合EE，V和E中的元元素分别别称为图图的端点点和边。下面用集集合论的的术语给给出图的的定义：设有集合合V和E，V=v1，v2，vn， EE=ee1，e2， emm ，且则V和E组成图图G，称称V为端集集，E为边集集。下面给出出图的一一些概念念: 当eij=(vi，vj)，称边边eij和端端vi与vj关联； 当viRvj不等价价于vjRvi时，为为有向图图； 当viiRvj等价于于vjRvi(eijj=ejii)时，为为无向图图；当V=(此时E必为空空集) ，为空空图；自环，孤孤立点图图，重边边；简单图: 不含含自环和和重边的的图称为为简单图图. 当V，EE均有限限元 V，E时，称称为有限限图。我我们一般般讨论的的都是有有限图，考考虑到实实数集的的不可数数性，任任何有限限图都可可以表示示为三维维空间的的几何图图形，使使每两条条边互不不相交，而而且边均均可用直直线来实实现。但但是若要要在平面面实现则则不一定定能办到到，稍后后我们会会给出平平面图的的概念。子图:若若A的端集集与边集集分别为为G的端集集与边集集的子集集，则AA为G的的子图。若若AÌG，且且A¹G，则则A为GG的真子子图。特特别地，当当A的端端集和GG的端集集相等，称称A为GG的支撑撑子图。由由端点子子集诱导导生成的的子图. 图图的运算算:G1ÈG22, GG1ÇG22, GGc等 图的几几种表现现形式: 集合合论定义义, 几几何实现现, 矩矩阵表示示.图的同构构; 权权图.2.1.2图的的连通性性 对对无向图图的端vvi来说，与与该端关关联的边边数定义义为该端端的度数数：，记记为：dd(vii)。对对有向图图：d+(vi)表示示离开vvi的边数数，d-(vi)表示示进入vvi的边数数对图G=(V，EE)，若若|V|=n，|E|=m，则则有如下下基本性性质： 1）若若G是无向向图 2）若GG是有向向图下面定义义图的边边序列，链链，道路路，环和和圈： 相邻二二边有公公共端的的边的串串序排列列（有限限） (v1，v2)， (v2，v3)， (v3，v4)，¼¼ (vi，vj)，称为为边序列列。边序序列中，无无重边的的，成为为链(llinkk)；若若边序列列中没有有重复端端，称为为道路(patth)；若链的的起点与与终点重重合，称称之为环环(riing)； 若若道路的的起点与与终点重重合,称称之为圈圈(cyyclee)。 任何二二端间至至少存在在一条径径的图，为为连通图图。否则则，就是是非连通通图。对对非连通通图来说说，它被被分为几几个最大大连通子子图，即即几个“部分”。“最大连连通图”指的是是在此图图上再加加任意一一个属于于原图而而不属此此图的元元素，则则此图成成为非连连通图，如如下例:G=AÈBBÈC=AA+B+C对于图的的连通, 可以以通过下下面的方方法给予予准确的的描述: 对对于图GG中的任任意两个个端点uu和v, 如如果存在在一条从从u到v的链, 称uu和v有关系系, 容容易知道道这是一一个等价价关系; 从而而可以将将图G做一个个等价分分类, 每一个个等价分分类就是是一个连连通分支支.连通通分支只只有一个个的图为为连通图图.下面举一一些图的的例子:(1)完完全图KKn：任任何二端端间有且且只有一一条边（即即直通路路由），称称为完全全图， 其边、端端数之间间存在固固定关系系: 下面是是一个nn=5的的完全图图(2)正正则图：所有端端度数都都相同的的连通图图为正则则图 d(vvi)=常常数（ii=1，22，¼n） 正则图图是连通通性最均均匀的图图(3)尤尤拉图(Euller): 端度度数均为为偶数的的连通图图为尤拉拉图。 尤拉拉图的性性质: 尤拉图图存在一一个含所所有的边边且每边边仅含一一次的环环.(4) 两部图图两部图的的端点集集合分为为两个部部分, 所有边边的端点点分别在在这两个个集合中中. 完完全两部部图Kmm,n(5)2.1.3树:树是图论论中一个个很简单单，但是是又很重重要的概概念，在在图论中中运用是是十分重重要的。图的定义义有多种种, 如如下面的的定义：1、 任何二端端有径且且只有一一条径的的图称为为树。2、 无圈的连连通图称称为树.我们采用用第2种种关于图图的定义义方式, 也就就是:树:无圈圈的连通通图称为为树.树有以下下性质: 1.树是最最小连通通图，树树中去一一边则成成为非连连通图。 2.树中一一定无环环。任何何二端有有径的图图是连通通图，而而只有一一条径就就不能有有环。 3.树的边边数m和端数数n满足m=n-11 此此式可以以用数学学归纳法法证明。 4.除单点点树，至至少有两两个度数数为1的的端(悬悬挂点) 树树上的边边称为树树枝 (braanchh)定理2.1：给给定一个个图T，若若p=|V|，qq=|EE|，则则下面论论断等价价：（1）TT是树；（2）TT无圈，且且q=pp-1；（3）TT连通，且且q=pp-1；证明：1）®2），显显然；2）®3），反反证：若若T不连连通，它它有k个个连通分分支（kk大于等等于2），每每个都为为树，若若第i个个树有个个点，则则，与q = pp-1相相矛盾；3）®1），pp=1时时，显然然。设，TT连通，且且q=pp-1，首首先易证证T有悬悬挂点，不不然，与与q = p-1相矛矛盾；然然后对点点数进行行归纳即即可；定理2.2：若若T是树树，则：（1）TT是连通通图，去去掉任何何一条边边，图便便分成两两个且仅仅仅两个个分图；（2）TT是无圈圈图，但但添加任任何一条条边，图图便会包包含一个个且仅仅仅一个圈圈。同时，若若无向图图满足（11）和（22），则则T是树树。定理2.3：设设T是树树，则任任何两点点之间恰恰好有一一条道路路；反之之，如图图T中任任何两点点之间恰恰好有一一条道路路，则TT为树。 定理22.2和和2.33刻画了了树的两两个重要要特征，事事实上定定理2.3也为为图提供供了另一一个等价价定义。上上述两个个定理的的证明请请读者自自行完成成。支撑树(Spaanniing Treee)： 考虑树树T是连连通图GG的子图图，TÌG，且且T包含含G的所所有端，称称T是GG的支撑撑树。 由定义义可知，只只有连通通图才有有支撑树树；反之之有支撑撑树的图图必为连连通图。一一般支撑撑树不止止一个， 连通图图至少有有一个支支撑树。支支撑树上上任二端端间添加加一条树树支以外外的边，则则形成环环(ciircuuit)。支撑撑树外任任一边称称支撑树树的连枝枝，连枝枝的边集集称为连连枝集或或树补(Cottreee)。不不同支撑撑树对应应不同连连枝集。 对非连连通图来来说，它它可以分分成K个最大大连通子子图，即即K个“部分”，每部部分各有有支撑树树。K个支撑撑树的集集合形成成图G的主林林，其余余的边为为林补。主主林的边边数称为为图的阶阶，用r表表示。主主林的连连枝数称称为空度度，用m表表示。有有如下关关系式： nn=n11+n2+¼+nkr=( nn1-1)+ ( n22-1)+ ¼+ ( nk-1)=n-km=m-nn+k 例如：k=3； r=11-3=88； m=122-111+3=42.1.4割(cutt) 割指的的是某些些子集(端集或或边集)。对连连通图，去去掉此类类子集，变变为不连连通。对对非连通通图，去去掉此类类子集，其其部分数数增加。 割分为为割端集集与割边边集。1、割端端与端集集设V是图图G的一个个端，去掉VV和其关关联边后后，G的的部分数数增加，则则称V是图G的割端端。去掉掉几个端端后，GG的部分分数增加加，这些些端的集集合称为为割端集集。有的的连通图图无割端端，这种种图称为为不可分分图。 对于连连通图, 在众众多的割割端集中中至少存存在一个个端数最最少的割割端集，称称为最小小割端集集。最小小割端集集，其任任意真子子集不为为割集。 最小割割端集的的端数目目，称为为图的联联结度。联联结度越越大，图图的连通通性愈不不易被破破坏。2、割边边集与割割集连通图GG的边子子集S，去去掉S使使G为不不连通，称称S为割割边集在众多的的割集中中边数最最少的割割集，称称为最小小割边集集。最小小割边集集的任一一真子集集不为割割边集。最最小割集集的边数数，称为为结合度度. 结结合度同同样表示示图的连连通程度度，结合合度越高高，连通通程度越越好。3、基本本割集与与基本环环（针对对连通图图讨论）1） 基本割集集设T为连连通图GG的一个个支撑树树，取支支撑树的的一边（枝枝）与某某些连枝枝，定可可构成一一个极小小边割集集，此割割集称为为基本割割集。即即：基本本割集是是含支撑撑树T之一个个树枝的的割集。基基本割集集有n-1个.下面一个个图来理理解基本本割集.支撑树TT= 连枝：， 则基本本割集：（，）， (，)，(，)， (，)2）基本本环T为连通通图G的一个个支撑树树，G-T的边边集为连连枝集。取取一连枝枝可与某某些树枝枝构成环环。这种种包含唯唯一连枝枝的环称称基本环环。每个基本本环只包包含一个个连枝-与与连枝一一一对应应，其数数目=连连枝数，共共m-nn+1个。环和运算算: 对对于集合合, 这这个运算算的意义义为对称称差运算算.通过环和和运算, 由基基本割集集和基本本环可以以生成新新的环和和割集或或它们的的并集,事实上上可以生生成所有有的环和和割集.例2.22 通过过基本环环和基本本割集理理解基尔尔霍夫定定律.下面的图图理解基基本环. 连枝枝集 ，：，：，：，：，2.1.5 图图的平面面性图G若可可以在一一个平面面上实现现，除端端点以外外，任何何两条边边均无其其他交点点，则称称G是平平面图。当当平面图图有一个个平面实实现后，它它把全平平面分成成s个区域域（含包包含无穷穷远点的的开区域域）。注注意一个个图为平平面图等等效于能能够在球球面上有有一个几几何实现现.设连通平平面图有有m边，n端，则则s=mm-n+2，此此为著名名的Euulerr公式。这这个性质质可以用用数学归归纳法证证明或树树的性质质证明。 m=44，n=4，ss=2定理2.4：简简单连通通图为平平面图的的必要条条件是:m<=33n-66 (n>=3)上述结论论可以推推广到有有重边和和自环的的情形.证：形成成区域至至少3边，区区域周线线上的边边数至少少3s(不考虑虑区域共共边)，实实际每边边均在二二区域周周线上，最最多有22m边（周周线上）。考考虑区域域共边，有有2m3ss，代入入Euller公公式得mm3n-6.此为平面面图的必必要，非非充分条条件。例2.33 讨论论完全图图K5和完全全两部图图K3,33的平面面性.定理2.5连通通两部图图为平面面图的必必要条件件是:m+4 <= 22n (n>>=3)根据每个个平面图图G=（VV，E），可可以生成成一个对对偶图GG'。G的每个个平面对对应于GG'的每个个顶点，GG中相邻邻的两个个面在GG'中有一一些边与与G中的两两个面的的每一条条边界的的边相交交，如下下图所示示。但是是简单平平面图的的对偶图图可能不不再是简简单图。定理2.6 图图G为平面面图当且且仅当  G不含含K5和K3,33或它们们的细分分图为子子图.2.1.6图的的矩阵表表示 很多时时候，需需要将图图表示在在计算机机中，这这就有了了图的矩矩阵表示示。下面面主要介介绍关联联阵和邻邻接阵。1 关联阵设图G有有n个端，mm条边，则则全关联联阵；端vi对对应于矩矩阵的第第 I行(共n行)；边ej对应于于第j 列(共m列);其中中:下面是一一个例子子说明关关联矩阵阵, 例2.44由A0可可以看出出:(1)第第i行非零零元个数数等于端端vi度数, 每列列有两个个1;(2)若若第i行均为为0元素，则则vi为孤立立端， G为非连连通图;(3)若若i行只有有一个非非O元，则则vi为悬挂挂端;(4)如如果将AA0中每一一个列中中的任一一个1改改为-11, 则则n行之和和0向量量，所以以最多只只有n-1行线线性无关关，A0秩最大大为n-1。将无向图图全关联联阵A0 中每每一个列列中的任任一个11改为-1， 再去掉掉任一行行，得到到关联阵阵A，为n-1m阶。A中的每每一个非非奇异方方阵对应应一个支支撑树。图图G的支撑撑树数目目可由以以下方法法得到：定理2.7(矩矩阵-树树定理)用AT表表示A的转置置, 无无向图GG的主树树数目t(G) = ddet(AATT)，注意上面面的定理理计算的的主树数数目为标标号树的的数目; 同时时n-11阶矩阵阵dett(AAAT)可以直直接写出出, 主主对角线线的元素素为相应应端点的的度数, 其余余位置为为-1或或0, 而这取取决于相相应的端端点之间间是否有有边.例2.55t(Kn) = ,t(Kn,mm) = mn-1nm-11.t(Kn) = 的计算算如下：继续例22.4: 共共有8种种支撑树树如下2.邻接接阵邻接阵是是表征图图的端与与端关系系的矩阵阵，其行行和列都都与端相相对应。令G=（V，EE）是m端，n边的的有向图图，其邻邻接阵其中，如：对于无向向图 ，因因此是邻邻接阵为为对称阵阵。我们可以以通过对对C的一些些计算，得得到图GG的性质质。如：计算CC的幂次次可得到到关于转转接径长长的一些些信息。若Cijj(2)=1则存存在k，使Cik× CCkj =1，即即Cik= Ckjj=1，ii，j之之间至少少有径，径径长为22；若Cij(22)=aa，则vi®vj间有a条径长长为2的径，若若Cij(22)=00，则vi®vj间无径径长为22的径；所以， Cij(2)即为vi®vj间径长为2即转接一次的径数。同理，若若Cij(3)=1， 则有vvi®vk®vs®vj，径长长为3，即经经过二次次转接。由此可得得下面结结论:邻邻接阵幂幂之元素素表示了了二端间间转接次次数不超超过b-1的的径，但是是经过转转接的端端可能重重复。已知图GG的邻接接阵C, 需需要解决决图G是是否连通通的问题题? 当当然通过过计算邻邻接阵CC和C的的幂可以以解决这这个问题题,考虑虑下面的的小算法法, 它它解决同同样的问问题, 但效率率很高.Warsshalll 119622(1)置置新矩阵阵 P:= CC;(2)置置 i = 11; (3)对对所有的的j, 如如果P(j,ii)=11, 则则对k=1,22,n P(jj,k):= P(jj,k)Ú P(i,kk);(4) ii = i+11;(5)如如n ³ ii转向步步骤(33), 否则停停止.本节介绍绍了图论论的简要要知识，1和和2介绍了了很好的的基础知知识。4介介绍了网网络优化化算法的的详尽的的和较新新的进展展。本节节内容同同时也借借鉴33的一一些结果果。某些些图论知知识在以以后应用用是会在在介绍。§2.22 最短径径问题上节中介介绍的图图只考虑虑了图顶顶点之间间的关联联性，本本节将要要对图的的边和端端赋予权权值，讨讨论有权权图。权权值在各各种各样样实际问问题中有有不同的的实际意意义，如如费用，几几何距离离，容量量等等。本本节将介介绍一些些算法，大大部分算算法可借借助计算算机实现现。§2.22.1 最短支支撑树给定连通通图G=(V，EE)，WW(e)是定义义在E上的非非负函数数，称WW(e)为e的权。TT=(VV，)为G的的一个支支撑树。定定义树TT的权为为。最短支支撑树问问题就是是求支撑撑树，使使W()最小。下下面介绍绍求最短短支撑树树的方法法。1) 无限制条条件的情情况 Priim在119577年提出出一个方方法，简简称P算法。 图G有有n端，端端间“距离”dij(i，jj=1，22，3，.n)已给定定(若无边边则diij=¥)，找一个支支撑树，使使其n-1个边边（树枝枝）的权权和最小小，步骤骤如下： P0:任取一一端v1，子图图G1=v1，在G1到G-GG1中取最最小的ddij得子图GG2= vv1， vv2P1:求求G3得子图GG3= vv1，v2，v3 PPr-22:从Gr-11求Gr 得子图GGr= vv1，v2，vvr Pr-1:重重复Pr-22，直至至得到GGn为止例2.55:G1=v1G2=v1，v3G3=v1，v3，v6G4=v1，v3，v6，v7G5=v1，v3，v6，v7，v2G6=v1，v3，v6，v7，v2，v5G7=v1，v3，v6，v7，v2，v5，v4则W(TT)=115可以看出出， PPrimm算法第第K步运算算，是以以Gk作为整整体寻找找至G-Gk的最短短边，每每次并入入Gk的边总总是保持持余下mm-k+1个中中最短的的，因此此算法终终止时，所所得的支支撑树为为最短者者(可用用数学归归纳法证证明)。 从算法法始至终终止，共共进行nn-1步步，每步步从k个端与与n-kk个端比比较，须须经k(n-kk)-11次，可可得总计计算量约为n33量级。当当n很大时时，可借借助计算算机实现现。另一个算算法由KKrusskall在19556年提提出:设G(kk)是GG的无圈圈支撑子子图,开开始G(0)=(VV,f)。若G(k)是连通通的,则则它是最最小支撑撑树；若若G(k)不连通通,取ee(k)为这样样的一边边,它的的两个端端点分属属G(k)的两个个不同连连通分图图,并且且权最小小。令GG(k+1)= G(kk)+ e(kk),重重复上述述过程。上面算法法的实现现过程需需要排序序算法；Roseensttiehhl和管管梅谷提提出了另另一个算算法：设G(kk)是G的连通通支撑子子图，开开始G(0)=G，若若G(k)中不含含圈，则则它是最最小支撑撑树；若若G(k)中包含含圈，设设m是G(k)中的一一个圈，取取m上的一一条权最最大的边边e(k)，令G(k+1)= G(kk)-ee(k)，重复复上述过过程。上面算法法的实现现过程需需要解决决如小问问题：对于一个个无向图图G, 如何寻寻找其中中的圈?可以通过过搜索图图中度为为1的顶顶点而逐逐步简化化.上面算法法的实施施过程,都是一一种贪心心法原理理的应用用; 从从局部最最优的结结果中寻寻找全局局最优的的结果.问题如如果复杂杂, 这这种方法法一般只只能找到到准最优优解.2) 有限制情情况 在许多情情况下，不不但要求求最短支支撑树，还还要求一一些额外外条件。有有两种解解决此类类问题的的方法穷穷举法和和调整法法。穷举举法就是是先把图图中的支支撑树穷穷举出来来，按条条件逐个个筛选，最最后选出出最短支支撑树。这这种方法法较直观观，但很很烦琐。下下面讨论论调整法法。以EEsauu-Wiilliiam算算法为例例(解决决一种特特定的问问题):问题:图G有nn个站,其中已已知v1是主机机，已知知各边间间距离ddij，以及各各个端站站的业务务量Fi（i，jj=1，22，nn），要求任任端至vv1的径边边数<K(即限限转接次次数<KK-1)，且且径上总总业务量量£M，(其其中K为为给定的的整数,M为给给定的实实数),求最短短支撑树树算法主要要思想:从上图开开始(星星形树),采用用贪心法法原则,逐步用用边替换换vi至v1的边,为此需需要计算算转接损损失矩阵阵, 每每次选用用一条边边使新树树的长度度减少最最多,但但每次要要注意新新树是否否满足限限制条件件。实质质上，每每次都和和上次得得到的树树做比较较，看看看能否有有进展。步骤：EW0：起始，nn个端为为n个部部分，邻邻接阵为为全零阵阵；EW1：计算到到v1各个部部分的距距离D11i，和不不在同一一个部分分内的两两端之间间的边的的转接损损失tiij EW22： 测试试增加边边(i*,j*)边后是是否仍满满足条件件，若满满足，在在邻接阵阵置 ；若不满满足，则则重复EEW2； EW33：考虑虑形成的的新的部部分，若若部分数数大于11，返回回；等于于1，终终止； 说明：若实例2.6(其其中K=3, M=550)：计算T矩矩阵：t34=-111 最小小，取边（33, 44）最替替换边(3, 1)；如此反复复，最后后得树为为: (3, 4), (4, 1), (22, 55), (5, 1)树长=112上面的例例中, 如果将将边(33, 22), (2,1)和和(4, 5)的权改改为2, 3.5和33.5, 容易易得到一一个简单单的反例例, 存存在一个个树长为为11的的支撑树树, 也也满足问问题中要要求的限限制条件件，说明明上述EEW算法法得到的的不是全全局最优优解.§2.22.2、端间间最短径径当网络结结构已定定，我们们需要寻寻找端间间的最短短距离和和路由。分分两种情情况：寻找指定定端至其其它端的的最短径径和路由由，我们们采用DDijkkstrra算法法；寻找任意意二端最最短径和和路由, 用FFloyyd算法法。1)指定定端至其其它端最最短径和和路由算算法:已知 图图G=(V，EE)及ddij，求端vvs至其它它端的最最短径和和路由，用Diijksstraa算法：由上图可可以看出出： 直边不不一定是是最短径径，如dds2，其其实vs与v2间最短短径长为为3(经经v3转接)。但可可肯定，与与vs相连的的直边最最小的一一个必定定为最短短径(如如es3)，其其它转接接至vs必不短短。因此此，算法法从始找找邻近端端， 从vvs最邻近近端找起起， 每每次得一一个最短短径。下面我们们介绍DDijkkstrra算法法，暂时时不考虑虑端有权权, 对对于端有有权的情情况稍后后处理; 首先先我们会会用到下下列计算算中的名名词：置定：某某端置定定即表示示得到了了至该端端的最短短径 标值：至至该步时时的暂时时最短径径，（置置定端可可供转接接） wi为为vs®vi暂时的的的最短短径长 wj*为vs®vi的置定定时的最最短径长长Dijkkstrra算法法步骤：端点集合合Vp表示置置定的端端点集合合, VV- VVp为没有有置定的的端点集集合;D0 开始置置定vss，ws*=0（vvs®vs），其其它端暂暂置wjj=¥( 如果果边(ss, jj)存在在, wwj= ds,j)D1 计算未未置定端端vj的标值值的公式式wj :=miin（wwj，wi +dijj）, 其中vviÎVp vvjÎV- VVpD2 取最小小值, wj*=minn wjj 然后后, 置置定端vvj*ÎVp ; 当所有有端置定定，算法法结束. 不然然, 返返回D11.上面的算算法没有有给出取取得最短短径的路路由, 不过对对于路由由可以很很简单处处理. 路由的的给出方方法可以以有许多多种, 如前向向路由和和回溯路路由等. 对于于Dijjksttra算算法, 可以给给出回溯溯路由, 即给给出最短短径的前前一个端端点的标标号, 而这个个端点标标号可以以在算法法D1的更更新计算算中获得得; 每每个端点点的标号号可以由由两部分分组成, 即距距离和前前一个端端点标号号. 例2.66：VsV11V2V3V4置定端 距离离 路路由0¥¥¥¥ 88 44 26 88 33 5656Vs 00 sV32 ssV23 3V45 33V16 22D算法计计算量:当有个个k端已置置定，需需做(nn-k)次加法法，(nn-k)次比较较以更新新各端的的暂定值值，(nn-k-1)次次比较求求最小值值，则总总计算量量约为对于Diijksstraa算法, 提出出若干问问题如下下: 1 如果端端点有权权如何处处理? 2 如果边边的权可可正可负负, 算算法是否否仍然有有效? 3 算法是是否对有有向图也也适用？上面Diijksstraa算法中中使用的的为Laabell-seettiing的的方法, 下面面介绍一一个用LLabeel-ccorrrecttingg技术的的方法, 效率率要高许许多。不失一般般性，假假设是GG一个有有向图，用用d(ii)记从从s至i的距离离，prred(i)记记路由ssi的上一一个顶点点(回朔路路由), A(i)记记录从ii出发的的所有边边的集合合。算法法如下：begiin d(ss):=0andd prred(s):=0; d(jj):=forr eaach jV-s; Lisst:=s; whiile Lisst ¹f do beggin从 Liist中中去掉一一个元素素i ;对每个边边(i, j)A(ii) ddoif dd(j)> dd(i)+Ciij theen beeginnd(j):= d(ii)+ Cijjpredd(j):=ii；if jÏLiist, thhen 将j并入Liist;end; endd; endd; 上面的算算法中没没有指明明Lisst的结结构, 如果将将Lisst组织织为一个个队列, 算法法效率会会更高, 计算算复杂度度为O(nm), 大大约为目目前最快快的算法法, 上面面两个算算法的解解决思路路的比较较是很有有意义的的。值得注意意的是，如如果附加加一些条条件，那那么问题题便很复复杂了。如如果边有有两个权权,相应应的算法法就复杂杂的多, 并且且很可能能无多项项式算法法.2、所有有端间最最短径算算法 Flooyd算算法解决决了图GG中任意意端间的的最短距距离和路路由，并并且也采采用Laabell-coorreectiing 的方法法。给定图GG及其边边 (ii, jj)的权权dij(ii，j=1，22，3，n);F0：初初始化距距离矩阵阵W(0)和路由由矩阵RR(0) ;W(0)= Wijj(0) n´n其元素：同时 RR(0)= rijj(0) n´nF1：已已求得WW(k-1) 和R(k-1)，求求W(k) 和R(k) ; wiij(kk)=mminwijj(k-1)，wwik(kk-1)+ wwkj(kk-1)F2：若若k<nn，重复复；k=n终止止。上面的路路由方法法为前向向路由，容容易更改改算法使使它的路路由为回回溯路由由; 算算法要执执行n次迭代代, 第第k次迭代代的目的的为经过过端k转接是是否可以以使各端端之间距距离缩短短. 从从本质上上讲, Flooyd算算法的迭迭代过程程就是保保证满足足下面的的定理成成立.定理2.8 对对于图GG, 如如果w(i, j)表表示端ii和j之间的的可实现现的距离离, 那么么w(ii, jj)表示示端i和j之间的的最短距距离当且且仅当对对于任意意i, k, j有:w(i, j) w(i, k) +w(k, j)Floyyd算法法计算量量 :wij(kk)=mminwijj(k-1)，wwik(kk-1)+ wwkj(kk-1)中，每每定一kk值，求求wij经11次加，11次比较较，求一次次迭代为为n2次加，nn2次比较较，共nn个迭代代，所以其其运算量量为n3级; 显然比比重复使使用Diijksstraa算法效效率高，同同时存储储效率也也要高。对于Flloydd算法, 同样样提出若若干问题题如下: 11 如果果端点有有权如何何处理? 22 如果果边的权权可正可可负, 算法是是否仍然然有效? 3 算算法是否否对有向向图也适适用？例2.77 给定定一个无无向图GG, 求求任意两两端之间间最少转转接次数数和路由由.例2.88图有六六个端，端端点之间间的有向向距离矩矩阵如下下：1. 用D算法法求V11到所有有其他端端的最短短径长及及其路径径。2. 用F算法法求最短短径矩阵阵和路由由矩阵，并并找到VV2至VV4和VV1至VV5的最最短径长长及路由由。3. 求图的中中心和中中点。解：1. D算法V1V2V3V4V5V6指定最短径长长,路由由0V1W100, 19 1 3V3W131, 193 2 V5W152, 38 3 7V4W143, 18 7 V3W167, 5 8 V2W128, 52. F算法最短路径径矩阵及及最短路路由阵为为W5，R5有向距离离为4有向距离离为23. 中心为为V3或V5中点为为V2 在实实际问题题中，除除了求最最短径外外，如当当主路由由（最短短径）上上业务量量溢出或或故障时时，需寻寻求次短短径或可可用径。次次短径指指备用径径，可用用径指一一批满足足某种限限制条件件的径（如如限径长长，限转转接次数数.）。但但这些问问题一般般没有多多项式算算法, 可以根根据实际际情况采采用某种种贪心策策略获得得近似解解.3、网的的中心与与中点如网络用用图G=(V, E)表示, 根据据Flooyd算算法的计计算结果果可以定定义网络络的中心心和中点点.中心:对每个端端点i, 先求求此值最小小的端称称为网的的中心，即即满足下下式的端端i*：=网的中心心宜做维维修中心心和服务务中心。中点:将“平均均最短径径长”最小的的端，定定义为中中点，先计算 si =, 然后后求出ssi的最小小值, 相应的的端点为为中点.网的中点点可用做做全网的的交换中中心。§2.33网络流流量问题题 网络的的目的是是把一定定的业务务流从源源端送到到宿端。流流量分配配的优劣劣将直接接关系到到网络的的使用效效率和相相应的经经济效益益。网络络的流量量分配受受限于网网络的拓拓扑结构构，边和和端的容容量以及及路由规规划。本本节及下下节中关关于流量量的内容容均在有有向图上上考虑，并并且均是是单商品品流问题题，即网网络中需需要输出出的只有有一种商商品或业业务。通通信网络络的服务务对象有有随机性性的特点点, 关关于通信信业务随随机性特特点将在在下一章章中考虑虑, 本本节中假假设网络络源和宿宿的流量量为常量量.§2.33.1基基本概念念 给定一一个有向向图G=（V，EE），CC(e)是定义义在E上一个个非负函函数，称称为容量量；对边边eij，边边容量为为Cijj ，表示每每条边能能通过的的最大流流量。设设f= fijj 是上上述网络络的一个个流，若若能满足足下述二二限制条条件，称称为可行行流。a)非负负有界性性：0fijCij；b)连续续性: 对端vvi有： vv(f) = F为源源宿间流流fiij的的总流量量.式中 （vi）=vj:( vvi， vvj)E 流流出vii的边的的末端集集合;(vvi)=vj: ( vj， vvi)E 流流入vii的边的的始端集集合; 有n个个连续性性条件，共共有2mm+n个个限制条条件，满满足上述述二限制制条件的的流称为为可行流流。 需要解解决的问问题分为为两类: 1 最最大流问问题在确定流流的源和和宿的情情况下, 求一一个可行行流f, 使v(ff) = F为为最大; 2 最最小费用用流问题题 如如果边(i,jj)的单单位流费费用为ddi,jj ,流f的费用用为: 所谓谓最小费费用流问问题: 在确定定流的源源和宿的的情况下下, 求求一个可可行流ff, 使使为最小小. 下面介介绍割量量和可增增流路的的概念. 设X是是V的真真子集，且且vsX，vvtXc，（X，XX