A OPTIMIZATION ALGORITHM BASED ON DIJKSTRA’S ALGORITHM IN SEARCH OF SHORTCUT

When shortcut between two nodes is searched with Dijkstra’s algorithm, a lot of nodes away from the shortcut are involved.So efficiency of Dijkstra’s algorithm is low. A optimization algorithm is presented in this paper based on Dijkstra’s algorithm in search of shortcut. Based on the idea of beeline distance, the formula for the disposition of nodes is changed in the optimization algorithm. In the course of the optimization algorithm running, only these nodes in the shortcut or close to the shortcut are processed, and those nodes away from the shortcut are not processed. So the number of processed nodes is largely reduced in the optimization algorithm. Efficiency of the optimization algorithm is improved. Validity of this algorithm is proved. Practicablity and efficiency about this algorithm are disscused. This algorithm has been applied in practical task.