一种基于二叉堆的Dijkstra最短路径优化方法

摘要：

本文针对Dijkstra算法在处理海量数据时,运算次数随着数据量增大而快速增大,运算效率显著降低的问题,使用最小二叉堆作为Dijkstra最短路径算法的辅助数据结构,有效降低算法的运算次数并提高运算效率.实验选取中国31个省会城市(不包括港澳台)的距离数据和火车直达性数据,数值结果显示采用二叉堆优化之后的算法,求取最短路径的实际时间比传统算法要少,而且随着问题规模的不断增大,两种算法的时间差越来越大,表明二叉堆优化的算法可以显著提高计算效率.

关键词：最短路径算法、二叉堆、算法优化、计算效率

所属期刊栏目：38

分类号：O224(运筹学)

在线出版日期：2022-10-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：709-720