在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2021, Vol. 38 ›› Issue (5): 709-720.doi: 10.3969/j.issn.1005-3085.2021.05.010

• • 上一篇    下一篇

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

王芝麟1,   乔新辉2,   马  旭2,   严  研2   

  1. 1. 国网陕西省电力有限公司，西安 710048
    2. 北京洛斯达数字遥感技术有限公司，北京 100120
  • 出版日期:2021-10-15 发布日期:2021-12-15

A Dijkstra Shortest Path Optimization Method Based on Binary Heap

WANG Zhilin1,   QIAO Xinhui2,   MA Xu2,   YAN Yan2   

  1. 1. State Grid Shaanxi Electric Power Company Limited, Xi'an 710048
    2. Beijing North-Star Digital Remote Sensing Technology Company, Beijing 100120
  • Online:2021-10-15 Published:2021-12-15

PDF (PC)

45

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

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

Abstract:

This paper is concerned with the problem that the calculations of Dijkstra algorithm increase rapidly with the amount of data. First of all, the minimum binary heap as the auxiliary data structure of Dijkstra shortest path algorithm is proposed, which can effectively reduce the  calculations and improve the operation efficiency. Then, the distance data and train accessibility data of 31 provincial capitals in China (excluding Hong Kong, Macao and Taiwan) are chosen in the numerical simulations. Finally, the results indicate that it is much faster to find the shortest path by applying the binary heap optimization algorithm than the traditional algorithms, and it is more obvious when increasing scale of the problem. It is conclued that the binary heap optimization algorithm is able to significantly improve the computational efficiency.

Key words: shortest path algorithm, binary heap, algorithm optimization, computational efficiency

中图分类号: