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

• 作者: 张祖平 王伟平 陈建二
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 网络路由 Dijkstra算法 Kruskal算法
• 年，卷（期）: 2002,（10）
• 所属期刊栏目: 短文
• 页码范围: 1116-1120
• 页数: 5页
• 分类号: TP301
• 字数: 4105字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.10.018

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
2	张祖平	中南大学信息科学与工程学院	85	617	13.0	21.0
3	王伟平	中南大学信息科学与工程学院	94	971	16.0	27.0