Comparing the pathfinding algorithms A*, Dijkstra’s, Bellman-Ford, Floyd-Warshall, and best first search for the paparazzi problem

Abstract

This paper aims to compare A*, Dijkstra, Bellmann-Ford, Floyd-Warshall, and best first search algorithms to solve a particular variant of the pathfinding problem based on the so-called paparazzi problem. This problem consists of a grid with different non-moving obstacles that lead to different traversing costs which are considered as minimization objective in a specific model. The performance of the algorithms that solve the paparazzi problem is compared in terms of computation time, the number of visited nodes, shortest path cost, and accuracy of finding the shortest path. The comparison shows that heuristic algorithms mostly provide the optimal path but with a shorter computation time.