Parallel implementation of A* search algorithm for road network
Safa Belhaous, Sohaib Baroud, Soumia Chokri, Zineb Hidila, Abdelwahab Naji, Mohammed Mestari · 2019
Path finding is a fundamental topic in artificial intelligence, which can be used in many problems and applications. There are several algorithms developed in order to find shortest path from source to destination. The most popular of them are A*, Dijkstra and ant colony optimization. This work is based on A* search algorithm to find the optimal path among cities with reduced time. Therefore, our parallel algorithm is implemented on a shared-memory multiprocessor system which many threads running simultaneously to find the path from each neighbor of start city to goal city. The number of threads generated depends on the number of starts neighbor. Experimental results are compared with the sequential A* to evaluate a path search performance between two nodes in a graph.