距离寻优中Dijkstra算法的优化

【文件属性】：
文件名称：距离寻优中Dijkstra算法的优化
文件大小：176KB
文件格式：PDF
更新时间：2011-08-10 08:14:57
Dijkstra算法 算法在求解两指定顶点间最短距离时, 对两顶点之间最短路径以外的大量顶点进行了计算, 而影响了算法的速度. 在对 算法分析的基础上, 结合网络模型的特点, 对 算法进行了优化. 优化算法基于两点之间直线最短的思想, 改变了对顶点处理顺序的规则. 在算法流程中只对最短路径上及其附近的顶点做了处理, 而与最短路径相距较远的顶点基本不涉及. 因此, 在优化算法中计算的顶点数量大幅减少, 提高了算法的速度. 给出了优化算法的正确性证明, 对优化算法的实用性和效率加以讨论. 优化算法在实际中已经得到应用.