一类度约束最小生成树问题的Dijkstra算法

• 作者: 袁卫东
• 来源期刊: 科学技术与工程
• 学科: 工学
• 关键词: 最大度 度约束 Dijkstra算法 最小生成树
• 年，卷（期）: 2010,（8）
• 所属期刊栏目: 论文
• 页码范围: 1898-1901
• 页数: 4页
• 分类号: TP393.02
• 字数: 3006字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-1815.2010.08.016

摘要

度约束最小生成树问题是网络设计和优化中的一个NP 难题.结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法.该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树.同时对算法的复杂度进行了分析.最后通过与其他算法的仿真比较和算例,表明了新算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	袁卫东	宝鸡职业技术学院基础部	7	11	2.0	3.0