距离寻优中Dijkstra算法的优化

被引：57

作者：

鲍培明

机构：

[1] 南京师范大学数学与计算机学院!南京

来源：

计算机研究与发展 | 2001年 / 03期

关键词：

Dijkstra; 算法; 优化; 最短距离;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：307 / 311

页数：5