Evaluation of Shortest Path Algorithms for Solving Mazes.

Authors

DOI:

https://doi.org/10.55632/pwvas.v90i1.352

Keywords:

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.

Author Biographies

Brian Crutchley, Shepherd University

Undergraduate student.

Department of Computer Science, Mathematics, and Engineering

Jason Rafe Miller, Shepherd University

Assistant Professor of Computer Science

Department of Computer Science, Mathematics, and Engineering

Downloads

Published

2018-04-02

How to Cite

Crutchley, B., & Miller, J. R. (2018). Evaluation of Shortest Path Algorithms for Solving Mazes. Proceedings of the West Virginia Academy of Science, 90(1). https://doi.org/10.55632/pwvas.v90i1.352

Issue

Section

Meeting Abstracts-Poster