Proceedings of the 3rd Annual International Conference on Electronics, Electrical Engineering and Information Science (EEEIS 2017)

Heuristic Pathfinding Algorithm Based on Dijkstra

Authors
Yan-Jiang SUN, Xiang-Qian DING, Lei-Na JIANG
Corresponding Author
Yan-Jiang SUN
Available Online September 2017.
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)

Volume Title
Proceedings of the 3rd Annual International Conference on Electronics, Electrical Engineering and Information Science (EEEIS 2017)
Series
Advances in Engineering Research
Publication Date
September 2017
ISBN
978-94-6252-400-2
ISSN
2352-5401
DOI
10.2991/eeeis-17.2017.59How to use a DOI?
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/).

Cite this article

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  -