求解有向必经节点最短路径问题的算法

An Algorithm for Solving the Shortest Path Problem of Directed and Necessary Nodes

摘要: 具有必经节点的最短路径问题有着广泛的实际应用。但是在有向图的情况下，很多算法会因为所求最优路径中的必经节点顺序与实际不符而不得不进行大量重复性计算。本文针对这种情况提出了一种求解有向图必经节点最短路径问题的算法，可以更早检验是否存在符合路径顺序要求的最短路径并进行有效求解。

Abstract: The shortest path problem with necessary nodes has a wide range of practical applications. However, in the case of directed graph, many algorithms will have to perform a lot of repetitive calculations because the order of the required nodes in the optimal path is not consistent with the reality. In this paper, an algorithm is proposed to solve the shortest path problem of required nodes in a directed graph, which can verify the existence of the shortest path conforming to the path order and solve the problem effectively.