Dijkstra Algorithm for a Kind of the Degree-constrained Minimum Spanning Tree Problem
Yuan Wei-dong · Science Technology and Engineering · 2010
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 the maximum degree constraint in network G.At the same time, the complexity of the new algorithm has been analyzed.The effectiveness is proved though an simulation comparement with the other algorithm.