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

(1. 国网陕西省电力有限公司，西安 710048; 2. 北京洛斯达数字遥感技术有限公司，北京 100120)

1 引言

Dijkstra 算法是一种典型的最短路径算法，可以在有向图中实现最短路径规划.它的出现，解决了当时十分棘手的动态路径规划问题[1].随着地理信息科学技术和计算机网络技术的发展，最短路径在今天的交通运输、物流仓储和城市规划等领域仍然发挥着巨大的作用.二叉堆是一种数据项按照升序或者降序进行排列的数据结构[2].在排序问题中，堆这种数据结构具有很好的效率和更低的时间复杂度.而堆这样的特性，刚好满足了Dijkstra 算法求解“最短路径”，因此，如果使用最小二叉堆这种数据结构来优化Dijkstra 算法，将会大大降低算法的时间复杂度[3].最短路径问题一直是地理信息科学、计算机信息科学和算法等领域研究中的一个热点话题[4].近年来，伴随着网络数据的井喷，最短路径问题的实时或近实时计算面临着新一轮的挑战[5].Dijkstra 算法有较大的改进空间.

最短路径问题是一个传统的数学问题，它的研究一直是地理信息科学和GIS 空间分析的热门话题，尤其是在资源分配、路线分析和设计等方向发挥着不可提到的作用[6-8].近年来，Dijkstra 算法已广泛应用于许多领域，如优化，图像处理和网格处理[9].随着交通和物流行业的快速发展变革，对Dijkstra 算法的高效运行提出了新的时代要求，关于求解最短路径问题的算法优化也一直是专家和学者的研究热点……