Abstract: 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.

Key words: dynamic pruning, depth first search, shortest path

摘要： 针对过必经节点集的最短路径问题，提出一种基于动态减枝策略的深度优先搜索算法（Depth First Search based on Dynamic Pruning，DP-DFS），该算法构建一个二维矩阵，每搜索一个节点，比较当前路径的权值和与矩阵中已保存的权值，如果当前路径的权值小于矩阵中保存的权值，则更新矩阵中权值为当前较小的路径权值，否则进行剪枝。该算法比较适合较大规模的图搜索，实验表明，必经节点个数在50以内时，利用该算法可以在30?s内找到一条近似最优的最短路径。

关键词: 动态剪枝, 深度优先搜索, 最短路径