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

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

Dijkstra algorithm for a kind of the degree-constrained minimum spanning tree problem

As it knows to all, the degree-constrained minimum spanning tree problem is a NP difficulty in the network design and optimization.Therefore, concerning about the characteristics of this problem, a new algorithm is presented, basing on the fundamental idea of the Dijkstra algorithm.With the given node being maximum degree assured by this new algorithm, and selecting the edge with the minimum weight in remaining edges every single time, finally it comes out the minimum spanning tree of the given node under t...