经过指定的中间节点集的最短路径算法

Algorithm for finding shortest path which must go through specified intermediate node set

目前研究最短路径的算法,多数只是针对从起点出发到达终点的情况。如果限制这条最短路径必须要经过某些指定的中间节点,则现有的一些算法就不再适用了。基于Dijkstra算法和贪心理论,给出了解决此类问题的方法。将相关节点集拆分成三个子集,分别求连通三个子集的局部最短路径,进而形成全局待选最短路径,通过筛选得到目标路径。通过理论分析算法的时间复杂度和实际编程实验确认了该算法的有效性。

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.