关于实际构造最大带宽路径算法的研究

摘要：

建立最大带宽路径一直是网络路由研究,尤其是在最近的网络QoS路由研究中的基本问题.在以往的文献中, 有人提出了利用修改的Dijkstra算法或修改的Bellman-Ford算法来构建最大带宽路径.该文给出了一个简单的证明,指出了最大生成树与最大带宽路径之间的特殊关系,证明了可以使用修改的Kruskal算法来构建最大带宽路径.文中给出了修改的Kruskal算法,并且与已有的Dijkstra算法作了性能上的比较.尽管从理论上说,Dijstra算法和Kruskal算法的时间复杂度具有同样的阶,但在多种不同网络结构上的模拟测试结果表明,用Kruskal算法构建最大带宽路径的实际运行比Dijkstra算法至少要快3倍,而且在实现上比Dijkstra算法更简单、灵活.

关键词：网络路由、Dijkstra算法、Kruskal算法

所属期刊栏目：25

分类号：TP301(计算技术、计算机技术)

资助基金：海外青年学者合作研究基金69928201;长江学者奖励基金

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1116-1120