Heuristic Pathfinding Algorithm Based on Dijkstra
Yan-Jiang SUN, Xiangqian Ding, Lei-Na JIANG · 2017
The problem of shortest path solution belongs to the classical algorithm problem, the Dijkstra algorithm has wide research and application, but there are still some shortcomings in practical applications.First of all, in order to solve the problem of low efficiency of Dijkstra algorithm, this paper adopts the way of small heap, it improves the efficiency and makes the time complexity reduce to O (nlogn); secondly, since Dijkstra is a single source shortest path algorithm, and cannot be better to solve the problem that the path has passing points, so, this paper presents a heuristic pathfinding strategy based on the improved Dijkstra algorithm.Under the restriction of passing points, with the distance between the source point and passing point as a elicitation, this paper solves the shortest path problem from the starting point to finishing point; in the end, this paper verify the effectiveness of this pathfinding strategy by experimental results.