求最大带宽路的一种新算法

《求最大带宽路的一种新算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、求最大带宽路的一种新算法：带宽是X络通信中重要的性能指标。带宽资源是有限的，为了使信息在X络中尽量快地进行传输，寻找最大带宽路就是一种重要的方法。目前有两种经典的求解最大带宽路的算法：修正Dijkstra算法和修正Kruscal算法。该文提出一种新的最大带宽路算法，称为M-SPFA算法。与前两种算法相比，该算法具有更低的时间复杂度(O(m))，理解容易，实现也更加简单。　　关键词：带宽；X络；最大带宽路；算法；路径　　中图法分类号：TQ015.3：A：1009-3044(2011)17-4035-03　　ANeforMaximumBandportantparame

2、terofunication.Itisnotinexhaustible.Inordertotransmitinformationintheportantmethodtoseekthemaximumbandstoservethispurpose:themodifiedDijkstraAlgorithmandthemodifiedKruscalAlgorithm.Thispaperproposesaneforcalculatingthemaximumbands,itnotonlyhasloeplexity,butalsoiseasiertounderstandanda

3、cplish.　　Keyaximumbands;path　　最大带宽问题不是一个新问题，它的研究可以追溯到上个世纪70年代的最大流问题。文献[1]中指出运用修改的Dijkstra算法可以在O（mlogn）时间内解决最大带宽问题（也称为瓶颈问题）。这个方法被广泛用于以后的最大流问题和X络QoS路由算法的研究中。　　文献[2]中，证明最大带宽路与最大生成树之间具有特殊的关系，指出利用修正的Kruskal算法也可在O（mlogn）时间内求出最大带宽路，并且比Dijkstra算法的效率更高。　　本文借鉴求解最短路问题的SPFA算法思想，提出一种求解最大带宽路的新方法，称为

4、M-SPFA算法。该算法与前两种经典的算法相比，代码实现更加简单，时间复杂度也更低。　　1预备知识　　给定一个无向图G=(V,E)，其中，V表示图G中的节点集，E表示图G中的边集。设n=

5、V

6、，m=

7、E

8、。E中的每一条边e=[u,v]对应一个带宽值b(e)=b(u,v)。r=v1v2…vk表示图G中的一条v1－vk路，其带宽值定义为b(r)=min{b(vi,vi+1)

9、1≤i＜k}。　　节点上或边上赋有权值的无向图（有向图）称为有权无向（有向）X络，简称无向（有向）X络。　　2修正Dijkstra算法　　Edmonds和Karp[1]指出，在G中给出一个源节点s

10、和目标节点t，可以通过改进的Dijkstra算法来构造从s到t的最大带宽路。　　下面给出了这种算法的具体步骤。其中数组元素P[v]记录最大带宽树中节点v的父节点，B[v]记录最大带宽树中从源节点s到节点v的路径带宽。集合F可以用一个优先队列的数据结构表示，支持最小化、动态插入、删除等操作，每步操作的时间为O（logn）。Dijkstra算法的复杂度为O（mlogn），故改进Dijkstra算法的时间复杂度也为O（mlogn）[1]。　　图1修正Dijkstra算法　　3修正Kruskal算法　　现在考虑另外一个问题，即无向X络中的最大生成树问题。这里用链路带宽作为

11、边的权值。图G的最大生成树T是指图在G的所有生成树中满足最大的生成树。　　文献[2]中证明了最大生成树和最大带宽路径的关系。　　定理3.1给定X络G，边e的带宽值为b(e),若T是G根据链路带宽的最大生成树，那么对于G中的任意两个节点s和t，树T中从s到t的唯一路径Pu就是X络G中从s到t的最大带宽路径。　　根据以上定理，可以基于最大生成树来建立最大带宽路径。不难得出，由最小生成树算法稍加修改即可获得最大生成树的算法。Kruskal算法[3]是应用广泛的一种建立最小生成树的算法，修改后用于构造最大生成树，具体步骤见图2。集合由Union-Find树结构表示，在一组

12、包括m个MakesSet中，Union和Find操作可在O（mlog*n）时间内完成（这里的n是集合中所有元素的个数），对于实际问题中的n，一般有log*n≤6。因此Kruskal算法的时间复杂度为t(m)+O（mlog*n），其中，t(m)=O（mlogn）是步骤1中对X络中的m条链路进行排序的时间。一旦构造了最大生成树T后，就可以在线性时间内找到T中从s到t的唯一路径。　　图2Kruskal算法用于构造最大生成树　　虽然Dijkstra算法和Kruskal算法时间复杂度的理论界限要优于O（mlogn），但那些最佳算法难于理解且实现上需要很多技巧。因此Dijks

13、tra算法