Graph-based Shortest Path Optimization D ijkstra Algorithm Improvement

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.