During my Data Structures and Algorithms lab course, I undertook the implementation of three shortest path search algorithms: Jump Point Search, A* search, and Dijkstra's shortest path algorithm. Subsequently, I conducted thorough testing using unittests and performed analyses on their time complexities and Big O notations.
The time complexity of Dijkstra's algorithm is O(n + m log n), where n is the number of nodes and m is the number of edges. The time complexity of the A* algorithm is defined as f(n) = g(n) + h(n), where n is the next node in the path, g(n) is the cost of the path from the starting node to node n, and h(n) is the heuristic function that estimates the cheapest path from node n to the goal. The time complexity of the Jump Point Search algorithm is better than that of the A* algorithm because it is an optimized variant of the A* algorithm.
- Githubgithub.com/tfhuhtal/pathfinding/
- StackPython / Poetry / Unittest
