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

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

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

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

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

5、el-correcting 的方法。 Floyd算法基于下面的定理,网的中心与中点 如网络用图G=(V, E)表示, 根据Floyd算法的计算结果可以定义网络的中心和中点。,例2.6 图G的距离矩阵如下，用FLOYD算法求任意端间最短径长和路由，并求中心和中点。,计算结果如下：,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.

6、00 1.70 9.20 100.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.00 R1= 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,W7= 0.00 2.50 2.00 1.20 7.90 5.60 0.50 2.50 0.00 3.50 3.70 10.40 3.10 2

7、.00 2.00 3.50 0.00 3.20 9.90 4.00 1.50 1.20 3.70 3.20 0.00 6.70 6.80 1.70 7.90 10.40 9.90 6.70 0.00 13.50 8.40 5.60 3.10 4.00 6.80 13.50 0.00 5.10 0.50 2.00 1.50 1.70 8.40 5.10 0.00 R7= 0 7 7 4 4 7 7 7 0 7 7 7 6 7 7 7 0 7 7 6 7 1 1 1 0 5 1 1 4 4 4 4 0 4 4 2 2 3 2 2 0 2 1 2 3 1 1 2 0,根据上面的计算结果，中心为v4中点为v7。 7.9 10.4 9.9 6.8 13.5 13.5 8.4 19.7 25.2 24.1 23.2 56.8 38.1 19.2 对于Floyd