Path planning algorithm under specific constraints in weighted directed graph
Qiyun Sun, Wanggen Wan, Guoliang Chen, Xiang Feng · 2016
At present, most of the path planning algorithms are only aimed at reaching the end point from the starting point. However, in practical applications, the existence of a variety of constraints increases the difficulty of path planning , so the Dijkstra algorithm, A* algorithm and other classical algorithms become no longer applicable in such a situation. In this paper, considering the various constraints in practical problems, we abstracted out such kind of path planning problem: In a weighted directed graph, paths need to be found which start from a source node, after passing through some specified intermediate nodes without repetition, and finally ends at a specified termination node. Based on Dijkstra algorithm and heuristic search principle, a feasible path planning algorithm is proposed with the new concept of “inspired hop count” to balance the path weight and search time.