Shaghayegh Fereidounfar - Alzahra University
Seyed Meysam Kermani - Sharif University of Technology

In this paper we introduce the draft of a new graph-based algorithm for optimizationof shortest path problem. Our algorithm is based on the Dijkstra and A* algorithm,which is usually used for path planning. It was tested on the shortest path planningProblem against Dijkstra classic implementation. The comparison of these resultsshowed that the proposed algorithm exhibited a promising convergence rate toward anoptimal solution. The time is the total length or time that we estimate for the shortestpath in a graph. In most of the tested cases, our proposed algorithm managed to find asolution faster than the A* algorithm; in five cases, the graph-based algorithm found asolution at the same time as the A* algorithm. Our results also showed that the mannerof priority calculation had a non-negligible impact on solutions, and that anappropriately chosen priority calculation could improve them.

dynamic programming, Dijkstra algorithm, A* algorithm, graph-basedalgorithm, shortest path planning, optimization.