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

摘要

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