Theoretical Approach on Assessing the Accuracy of the Shortest Path Non-Optimal Algorithm for 2-Dimensional Grids with Obstacles
C. D. Mo · 2024
In many applications such as urban navigation and robotics, finding the shortest path in a 2D grid is crucial but computationally expensive using traditional optimal algorithms like Floyd-Warshall or Dijkstra. These traditional algorithms guarantee to find the shortest path at the cost of time complexity, leading to a time-consuming computation, particularly for large-scale grids. Non-optimal algorithms that trade accuracy for speed have emerged to address the issue. However, the impact of grid obstacle density on the accuracy of the algorithms has not been well understood. This paper presents a theoretical framework for evaluating the accuracy of two non-optimal algorithms. By integrating theoretical analysis with extensive experimental data, this paper demonstrates how obstacle density influences algorithm performance, and proposes a methodology to select the best non-optimal algorithms based on the grid obstacle density. The theoretical framework has practical implications for applications requiring rapid path finding in complex environments.