Heuristic Pathfinding Algorithm Based on Dijkstra

DOI

10.2991/eeeis-17.2017.59How to use a DOI?

Keywords

Dijkstra algorithm, shortest path, small heap, passing point, heuristic, pathfinding

Abstract

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 path-finding 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.

Copyright

© 2017, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Yan-Jiang SUN
AU  - Xiang-Qian DING
AU  - Lei-Na JIANG
PY  - 2017/09
DA  - 2017/09
TI  - Heuristic Pathfinding Algorithm Based on Dijkstra
BT  - Proceedings of the 3rd Annual International Conference on Electronics, Electrical Engineering and Information Science (EEEIS 2017)
PB  - Atlantis Press
SP  - 421
EP  - 425
SN  - 2352-5401
UR  - https://doi.org/10.2991/eeeis-17.2017.59
DO  - 10.2991/eeeis-17.2017.59
ID  - SUN2017/09
ER  -