关键词: Dijkstra算法, 贪心算法, 动态规划, 最短路径, 相关节点

Abstract: The vast majority of researches about the shortest path algorithm, nowadays, focus just on the case starting from the beginning point and ending at the ending point. If additional condition that the shortest path must go through some given nodes of which number is uncertain must be met, then most of the existing classic algorithms are not applicable. A general method based on the classical Dijkstra algorithm and greedy algorithm is presented to solve this kind of problem. The main method is to split the relevant node set into three sub sets, find the local shortest path of connecting the three subset separately to form the global shortest path to be selected, obtain the target path through screening. The time complexity of the algorithm is given by theoretical analysis and the effectiveness of the algorithm is verified by programming calculation.

Key words: Dijkstra algorithm, greedy algorithm, dynamic planning, shortest path, pruning algorithm