一种基于改进型Dijkstra算法的路线规划方法研究

发布时间：2024-02-01 11:16

　　文章较为详细地介绍了路线规划的基本概念、数据需求、常用算法,并实现了一种基于二叉堆结构的改进型Dijkstra算法,对其数据组织以及节点预操作进行了描述,对其空间复杂度和时间复杂度进行了理论分析,同时通过试验进行证明。试验结果可以看出基于二叉堆结构的改进型Dijkstra算法在数据量很大、稀疏度很高时,其计算速率明显优于传统Dijkstra算法。

【文章页数】：4 页

【文章目录】：
0 引 言
1 路线规划数据需求
2 路线规划算法
    2.1 传统Dijkstra算法
    2.2 A*算法
    2.3 Boost Graph Library
3 基于二叉堆结构的Dijkstra算法
    3.1 算法思想
    3.2 数据组织和数据存储
    3.3 节点排序和最短路径节点的选取
    3.4 空间复杂度分析
    3.5 时间复杂度分析
    3.6 基于二项堆结构的Dijkstra算法
    3.7 基于Fibonacci堆结构的Dijkstra算法
4 试验验证及分析
5 结束语



本文编号：3892022