Evaluation of Shortest Path Algorithms for Solving Mazes.
DOI:
https://doi.org/10.55632/pwvas.v90i1.352Keywords:
graph algorithms, shortest path,Abstract
Finding the optimal path through a maze is related to the shortest path problem in computer science. The first shortest path algorithm was introduced by Edsger W. Dijkstra in 1956 but multiple other solutions and optimizations have been suggested since then. We tested several algorithms for their applicability to the problem of solving mazes. We programmatically generated random 2D square mazes with independent variables for size and bias, where bias measures the deviation from random probability that a left or right turn contributes to a shorter path. We programmatically transformed each maze into a directed graph with arbitrary start and end positions and then solved for the shortest path through each graph. We speculated that maze bias, which tends to alter the graph density, would affect algorithm efficiency. We detected bias-dependent differences in resource usage between standard implementations of three shortest-path algorithms: Dijkstra’s, Bellman-Ford, and A*. Our results could help guide algorithm selection for robotic exploration of specific terrains given prior knowledge of their path properties. This project was supported by the NASA WV Space Grant Consortium.
Downloads
Published
How to Cite
Issue
Section
License
Proceedings of the West Virginia Academy of Science applies the Creative Commons Attribution-NonCommercial (CC BY-NC) license to works we publish. By virtue of their appearance in this open access journal, articles are free to use, with proper attribution, in educational and other non-commercial settings.