Dijkstra最短路径算法优化策略

详细信息   全文下载|推荐本文 |

• 出版年：2009
• 作者：张锦明；洪刚；文锐；王学涛
• 单位1：信息工程大学测绘学院
• 出生年：1976
• 学历：博士生
• 职称：讲师
• 语种：中文
• 作者关键词：最短路径；Dijkstra算法；优化策略
• 起始页：105
• 总页数：4
• 刊名：测绘科学
• 是否内版：否
• 刊频：双月刊
• 创刊时间：1976
• 主管单位：国家测绘局
• 主办单位：中国测绘科学研究院
• 主编：林宗坚
• 地址：北京市海淀区北太平路16号
• 邮编：100039
• 电子信箱：niu@casm.ac.cn
• 网址：http://chkd.chinajournal.net.cn
• 卷：34
• 期：5
• 期刊索取号：P810.6 649-8
• 数据库收录：俄罗斯文摘杂志收录期刊；日本科学技术社数据库期刊；美国剑桥科学文摘收录期刊；全国中文核心期刊；中国科技核心期刊；中国科学引文库核心期刊
• 核心期刊：全国中文核心期刊；中国科技核心期刊；中国科学引文库核心期刊

摘要

从分析经典Dijkstra最短路径算法出发，找出影响其效率的关键步骤：存储空间和时间效率，并结合当前已有的各种优化算法，总结出Dijkstra最短路径算法的优化策略：相关边优化策略、相关邻接结点优化策略、结点分类优化策略、权值排序优化策略、结点排序优化策略和单链结点剔除优化策略。最后，以实例运算表明优化策略是有效的，既节约了存储空间又提高了时间效率。