Analyzing and comparing routing algorithms to find the shortest path in graph transformable problems

Search is a problem solving technique in artificial intelligence. Graph search problems are often modeled as graph games between multiple agents. Graph search algorithms are designed with two main applications of graph traversal and finding the shortest path between two vertices of a graph. In this article, first a comprehensive study on search methods has been conducted and then, various route search algorithms have been investigated and compared in order to achieve the most optimal algorithm in finding the shortest route. These algorithms include Dijkstra, A*, and IDA* search algorithms, which have been compared with each other using the three parameters of execution time, time complexity, and space complexity. To carry out investigations, a hypothetical game state (field) was used in two conditions, with and without obstacles, and programming was done using Python programming language. The results show that the Dijkstra algorithm and the A* algorithm have relatively the same time complexity, and the IDA* algorithm is faster than both; Also, the IDA* method occupies less memory than the A* method.