距离寻优中Dijkstra算法的优化

摘要

When shortcut between two nodes is searched with Dijkstra'salgorithm, 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.%Dijkstra算法在求解两指定顶点间最短距离时，对两顶点之间最短路径以外的大量顶点进行了计算，而影响了算法的速度.在对Dijkstra算法分析的基础上，结合网络模型的特点，对Dijkstra算法进行了优化.优化算法基于两点之间直线最短的思想，改变了对顶点处理顺序的规则.在算法流程中只对最短路径上及其附近的顶点做了处理，而与最短路径相距较远的顶点基本不涉及.因此，在优化算法中计算的顶点数量大幅减少，提高了算法的速度.给出了优化算法的正确性证明，对优化算法的实用性和效率加以讨论.优化算法在实际中已经得到应用.