Two improved optimum path planning algorithms

An improved Dijkstra's and an improved A^* algorithm were proposed based on the analysis of their drawbacks. In the traditional Dijkstra's algorithm, the distance between two unconnected nodes is infinite and some relative calculations are useless. The improved Dijkstra's algorithm proposed that the connection between nodes should be tested at first so that it can decrease the computing overhead to a great extent. When the traditional A^* algorithm is used in practice, its efficiency is not satisfied. The improved A^* algorithm includes such steps as the following:firstly, the original optimum path should be planned by the traditional A^* algorithm; secondly the nodes in the original optimum path; should be blocked in turn and the traditional A^* algorithm is used again in order to look for another new optimum path, finally, these new optimum paths should be compared with the original one so that the final optimum path can be selected. Simulation results show that the improved Dijkstra's algorithm can enhance the calculation efficiency and the improved A^* algorithm can find the more optimum path.