%0 Journal Article
%A YAO Bo1
%A FENG Hongwei1
%A GAO Yuan2
%A MA Jiali1
%A FENG Jun1
%T Dynamic pruning search algorithm that must go through certain node set
%D 2017
%R 10.3778/j.issn.1002-8331.1610-0296
%J Computer Engineering and Applications
%P 57-62
%V 53
%N 15
%X A depth first search algorithm based on dynamic pruning strategy is presented to solve the problem of shortest path must go through some certain nodes. This algorithm constructs a two-dimensional matrix, it is need to compare the weight of current node and the saved matrix when visits a node. If the weight of current node is less than that in matrix, update the weight in matrix as the mix weight, or prune. The algorithm is suitable for large scale graph, experiment shows that when the number of must go through nodes is less than 50, the algorithm can find an approximateshortest path in 30 s.
%U http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.1610-0296