通信网理论基础第二章 通信网拓扑结构分析2.ppt

《通信网理论基础第二章 通信网拓扑结构分析2.ppt》由会员分享，可在线阅读，更多相关《通信网理论基础第二章 通信网拓扑结构分析2.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.2 最短径问题n 上节中介绍的图只考虑了图顶点之间的关联性，本节将要对图的边和端赋予权值，讨论有权图有权图。权值在各种实际问题中有不同的实际意义，如费用，几何距离，容量等。本节将介绍一些网络算法，包括最小支撑树和最短路径等算法。2.2.1 最小支撑树 n 给定连通图G=(V，E)，W(e)是定义在E上的非负函数，称W(e)为e的权。树 为G的一个支撑树。定义树T的权为 。n 最小支撑树问题就是求支撑树 ，使 最小。这类问题分为两类：有限制和无限制的情形。下面介绍求无限制时的最小支撑树的方法。下面的方法由Prim(1957)提出。另一个算法由Kruskal在1956年提出:n 设G(k)是G

2、的无圈支撑子图,开始G(0)=(V,)。若G(k)是连通的,则它是最小支撑树；若G(k)不连通,取e(k)为这样的一边,它的两个端点分属G(k)的两个不同连通分支,并且权最小。令G(k+1)=G(k)+e(k),重复上述过程。n 这个方法可以称之为避圈法，同时需要将图的所有边排序。Rosenstiehl（1967）和管梅谷（1975）提出了另一个算法：n 设G(k)是G的连通支撑子图，开始G(0)=G，若G(k)中不含圈，则它是最小支撑树；若G(k)中包含圈，设是G(k)中的一个圈，取上的一条权最大的边e(k)，令G(k+1)=G(k)-e(k)，重复上述过程。n 这个方法被称之为破圈法，同时

3、需要解决下面这个小问题。n问题：给定一个图，如何寻找这个图的圈？2.2.2 端间最短径 n 当网络拓扑结构已定，我们需要寻找端间的最短距离和路由。分两种情况：n寻找指定端至其它端的最短路径和路由，这个问题由Dijkstra算法解决；n寻找任意二端最短路径和路由,这个问题用Floyd算法解决。指定端至其它端最短路径和路由算法nn对于Dijkstra算法,提出若干问题如下:n1如果端点有权如何处理?n2如果边的权可正可负,算法是否仍然有效?n3算法是否对有向图也适用?n 4路由如何给出?n上面的算法没有给出取得最短路径的路由,不过对于路由可以很简单处理.路由的给出方法可以有许多种,如前向路由和回溯

4、路由等.对于Dijkstra算法,可以给出回溯路由,即给出最短路径的前一个端点的标号,而这个端点标号可以在算法的更新计算中获得。n n值得注意的是，如果附加一些条件，那么问题便很复杂了。如果边有两个权,相应的算法就复杂的多,并且很可能无多项式算法。nDijkstra算法中使用的为Label-setting方法,下面介绍一个用Label-correcting技术的方法,效率要高许多。n不失一般性，假设是G一个有向图，用d(i)记从s至i的距离，pred(i)记路由si的上一个顶点(回朔路由)。nn所有端间最短径算法nFloyd算法解决了图G中任意端间的最短距离和路由，也采用Label-corre

5、cting的方法。nFloyd算法基于下面的定理n网的中心与中点n如网络用图G=(V,E)表示,根据Floyd算法的计算结果可以定义网络的中心和中点。n例2.6图G的距离矩阵如下，用FLOYD算法求任意端间最短径长和路由，并求中心和中点。n计算结果如下：W1=0.00 100.00 100.00 1.20 9.20 100.00 0.50 100.00 0.00 100.00 5.00 100.00 3.10 2.00 100.00 100.00 0.00 100.00 100.00 4.00 1.50 1.20 5.00 100.00 0.00 6.70 100.00 1.70 9.20 1

6、00.00 100.00 6.70 0.00 15.60 9.70 100.00 3.10 4.00 100.00 15.60 0.00 100.00 0.50 2.00 1.50 1.70 9.70 100.00 0.00R1=0 2 3 4 5 6 7 1 0 3 4 5 6 7 1 2 0 4 5 6 7 1 2 3 0 5 6 1 1 2 3 4 0 6 1 1 2 3 4 5 0 7 1 2 3 1 1 6 0 nW7=n0.002.502.001.207.905.600.50n2.500.003.503.7010.403.102.00n2.003.500.003.209.904.0

7、01.50n1.203.703.200.006.706.801.70n7.9010.409.906.700.0013.508.40n5.603.104.006.8013.500.005.10n0.502.001.501.708.405.100.00nR7=n0774477n7077767n7707767n1110511n4444044n2232202n1231120根据上面的计算结果，中心为v4中点为v7。n 7.9 10.4 9.9 6.8 13.5 13.5 8.4n 19.7 25.2 24.1 23.2 56.8 38.1 19.2n对于Floyd算法,同样提出若干问题如下:1如果端点有权如何处理?n2如果边的权可正可负,算法是否仍然有效?n3算法是否对有向图也适用？n 4前向路由和回朔路由。n问题：给定一个无向图G,求任意两端之间最少转接次数和路由。