单源最短路问题高效算法探究

• 作者: 杨雷
• 来源期刊: 电脑知识与技术
• 学科: 工学
• 关键词: 最短路 迪杰斯特拉 数据结构 标准模板库 优化算法
• 年，卷（期）: 2009,（13）
• 所属期刊栏目: 软件设计开发
• 页码范围: 3439-3442
• 页数: 4页
• 分类号: TP312
• 字数: 3844字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-3044.2009.13.046

摘要

单源最短路问题是算法研究中由来已久的一个问题,在算法领域早期已经得到了较好的解决,但是在应用计算机语言实现的过程中往往不够优化,导致较高的时间复杂度和空间复杂度.从原始的迪杰斯特扭算法入手,进行透彻分析,在算法思想和实现方式上提出一种全面优化的算法方案,并给出了核心代码.实现过程中使用了堆的数据结构.并在具体的实现过程中进行灵活的优化.经过理论的算法复杂度分析,以及实际的数据测试,都证明全新优化后地单源最短路算法计算耗时非常少,空间复杂度也得到很大程度的降低,应用价值更强.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨雷		3	7	2.0	2.0