交通运输网络的二叉堆索引及路径算法优化

王 亚，任 燕，夏林元

1.遵义师范学院信息工程学院，贵州遵义563000

2.中山大学地理科学与规划学院，广东广州510275

交通运输网络是对提供物资输送且具有点线连通的网状地物的模型简化.节点实体、弧段实体及网络拓扑关系构成交通运输网络的基本模型要素.交通运输网络分析最常见的应用场景是交通运输网络的最短（或最优）路径分析.

在交通运输网络的最短路径算法研究中，基于道路交通网络的研究是最广泛的，文献[1-2]对道路交通网络的最短路径算法按目标向导和层次化两种类型进行了讨论.目标导向方法主要是通过引导路径的搜索方向来减少算法的搜索空间，该方法并不改变数据本身的性状.层次化方法则通过道路网的等级属性以及交叉口（可视为交通运输网络的节点）的连通性将一个网络分割成为相互连通的多层次网络，高层次的网络弧段量依次变少，最低层次的网络包含全部的弧段和节点实体，因此算法可以在不同的层次网络间切换搜索路径，从而降低搜索空间.上述文献虽然给出了算法间的性能比较，但算法的实现效率跟实际所采用的数据结构和内容密切相关，而这些文献并没有进行深入的研究.文献[3]在有向带权联通图的数据基础上对Dijkstra 算法进行了改进，针对不联通两点可能形成死循环的问题设计了相应的退出机制，并提出了如何求取最短路径上节点的相邻点的方法.该方法采用通用数据库的方式来记录图结构，类似于邻接矩阵的实现方式.显然，采用冗余的邻接矩阵方式来实现Dijkstra 算法的运算效率较低.文献[4]对A∗算法的估计函数进行改进，增加了一个从当前节点的上一个节点到目标节点的欧氏距离估算过程.在具体实现过程中，该改进算法采用了邻接表进行存储并利用优先级队列来实现.然而，采用欧氏距离作为A∗算法的距离估算函数，其计算效率会明显降低.文献[5]指出，采用邻接矩阵的方法存储网络拓扑数据的空间复杂度为O(N2)（N为交通运输网络的节点数目）.以Dijkstra 算法为例，当采用k叉堆、二项堆或Fibonacci 堆来实现时，其算法复杂度为O(MlgN)或O(M+NlnN)（M为交通运输网络的弧段数目）.当采用桶结构基数堆实现时，在弧段权重为整数的条件下，算法复杂度为O(M+NlnC/ln lnC)（C为常数），而基数堆和Fibonacci 堆相结合的算法复杂度仅为O(M+NlnC).文献[6-8]提出了一种基于模糊神经网络的最短路径算法，利用神经元间的并行性特征减少计算的迭代次数，从而取得优于Dijkstra 算法和A∗算法的计算效率，但文献未提及A∗算法作为比较基准时应该采用哪种估算函数来实现其计算过程.文献[9-11]提出了动态交通网络的数学模型，并设计了考虑交叉口延时的动态最短路径算法，在Hadoop 的MapReduce 算法框架下实现了最短路径并行计算算法.文献[12-13]讨论了基于不同交通工具的多约束条件的最短路径算法，并对Dijkstra 算法进行了相应的改进.

综合考虑主要的最短路径算法，文献[4,14-16]提及的Dijkstra 算法是目前应用最广泛的最短路径算法，也是求单源、无负权最短路径的较好选择，其计算的时间复杂度为O(N2+M).在算法设计过程中，Dijkstra 算法计算了从源点到搜索空间内所有其他节点的最短路径，而在具体的算法实现中只需要考虑从源点到目标节点的一条最短路径，因此该算法具有很大的改进可能.Floyd 算法[17]在求多源、无负权边的最短路径时，用节点矩阵来表示图，其时效性较差，时间复杂度O(N3).当采用Bellman-Ford 算法[18]求取单源最短路径时，可以对具有负权回路的图进行计算，时效性较好，时间复杂度为O(NM).A∗算法[19-21]是解决图中两顶点之间最短路径的一种最有效的启发式直接搜索方法，该算法实际上可看作是在Dijkstra 算法基础上引入了一个当前节点与目标节点的距离估算值.因为估算值具有引导作用，算法并不需要搜索所有的邻接节点，而是直接沿估算值的方向逼近目标节点，所以搜索速度明显加快.

基于上述分析，本文引入二叉堆索引结构对Dijkstra 算法和A∗算法进行了改进，提高了交通运输网络存储结构的读取效率，并通过数据类型的低精度损耗简化和运算类型的简化提高了算法的计算效率，尤其对A∗算法的估计函数进行了计算方式的优化，有效降低了搜索空间，从而提高了两种算法的整体计算效率.

1.1 交通运输网络的最短路径算法分析

本文首先结合图论的概念对交通运输网络进行分析.在图论中，图被定义为

式中，V为顶点的非空有穷集合V=(v1,v2,···,vn)，E为边的集合E=(e1,e2,···,en).根据边是否有序可将图分为有向图和无向图.在地理信息系统（geographic information system,GIS）网络中，资源的输送是具有方向性的，即使在道路交通网络中，双向通行的道路也可以简化为方向相逆的两条有向道路.因此，交通运输网络可以视为有向图，图中的顶点即为交通运输网络的节点实体，图中的边即为交通运输网络的弧段实体.交通运输网络中节点实体和弧段实体的网络拓扑关系可以用有向图中顶点的出度以及从顶点出发的边的集合表示.交通运输网络的约束包括两种：某条边的禁行和相互连接的多条边的禁行.以实际情况为例，某条道路由于施工禁止通行就属于第1 种约束，路口禁止掉头就属于第2 种约束.这两种约束在图论里并没有相关概念可以描述，本文将第1 种约束用边的禁行子集表示，将第2 种约束用连续边的禁行子集表示.在具体应用中，连续边可以采用链表结构实现.

根据以上分析可将交通运输网络（以下简称网络）定义为

式中，V为网络G中节点实体的集合，E为网络中弧段实体的集合，R1为G上的禁行弧段的集合，R2为G上的禁行连续弧段的集合.

1.1.1 Dijkstra 算法

根据以上定义，同时考虑到最终的计算结果是以连续弧段组成的路线来表示的，于是可以将交通运输网络中两节点实体之间的最短路径计算简化为两弧段实体之间的最短路径：给定起始弧段s ∈E和目标弧段t ∈E，计算s弧段到t弧段的最短路径p.

在交通运输网络中，Dijkstra 算法的运算逻辑如下：

令起始弧段的集合s={ei}，将初始化弧段设为e1，剩余网络弧段集合s−={e2,e3,···,en}，则有第1 条弧段到第1 条弧段（即其本身）的初始化最短路径为0，起始弧段到终点弧段的初始化最短路径为无穷大，即

式中，L为上一弧段到起始弧段的路径长度函数，T为当前弧段到起始弧段的路径长度函数.

实现Dijkstra 算法的具体步骤如下：

步骤1对ej ∈s−，ej R1，求min{T(ej),L(ei)+lij}=T(ej).

步骤2求时对应的T(er)，令L(er)=T(er).

步骤3若er=et，则已找到e1到et的最短距离L(er)，否则令i=k，从s−中删除ej后转步骤1，这样经过有限次迭代就可求出s到t的最短路径.

经分析可知Dijkstra 算法的基本思想是：从起始节点开始循环计算源节点到未标记节点的最短路径，直到找出所有未标记节点到起始节点的最短路径为止，其搜索范围可近似为以起始节点为圆心的一个圆形区域，如图1所示.

图1 Dijkstra 算法的搜索空间Figure 1 Searching space of Dijkstra algorithm

1.1.2 A∗算法

交通运输网络中A∗算法逻辑和具体步骤与Dijkstra 算法相似，在此不再赘述.A∗算法可以视为Dijkstra 算法的一种特例，其特殊之处在于A∗算法在计算最短路径时增加了当前节点到目标节点的距离（或权重）估算函数Dj→t.因此，在搜索过程中，A∗算法会沿着距离估算最小的方向逼近目标节点，其搜索范围可近似为以源节点与目标节点连线为中轴的椭圆形区域，如图2所示.

图2 A∗算法的搜索空间Figure 2 Searching space of A∗algorithm

1.2 交通运输网络的二叉堆索引结构

Dijkstra 算法的关键步骤在于循环地从未标记节点中选取权重最小的弧段.因此，如何组织节点及其相关弧段的数据结构，使得每次都能最快找到未标记节点中权重最小的弧段成了实现算法的关键问题.Dijkstra 算法的搜索范围可以看成以源节点为母节点向四周延伸的树状结构.此外，每次计算最短路径的源节点各不相同，因而该树状结构的母节点均不同，且母节点之下的子节点及其结构也都不同，这意味着每次计算都要重新组织一次数据的索引结构.同理，A∗算法虽然增加了估算函数，其基本搜索过程仍然是从源节点指向目标节点的树状延伸过程.因此，无论是Dijkstra 算法还是A∗算法，都可以考虑将其网络数据的索引组织成树状结构.在道路交通网络的应用中，其网络数据呈现的是稀疏有向图的特点.每个节点的出度一般不超过5，大部分为2 或者3，因此采用二叉树的索引结构的表示方式能够保证树的平衡性.目前，在最短路径搜索的研究中，最常见的几种网络数据组织结构主要有邻接矩阵、邻接表、链表等.表1比较了几种数据结构的操作效率.从表1可以发现，二叉树结构在查找、插入和遍历的效率方面优于其他数据结构.

表1 交通运输网络的数据结构操作效率比较Table 1 Comparison for efficiency of transportation network data structure

根据上述分析，本文设计了如图3所示的交通运输网络数据结构.一个交通运输网络由一个弧段数组和一个节点数组构成，每个弧段类的主要属性包括弧段ID、头节点ID、尾节点ID、弧段权重、弧段在弧段数组里的位置.每个节点类的主要属性包括节点ID、节点出度、以节点为出发点的第1 条弧段在弧段数组里的位置.弧段数组采用C++ 标准模板库STL 的Vector 类实现，数组内对所有弧段实行双重初始排序，首先是以弧段的头节点ID 进行排序，其次是将相同头节点的弧段依次排序.节点数组采用STL 的Map 类实现，Map 类的键（Key）为节点ID，值（Value）为节点对象.Map 内部的节点对象无需排序，直接通过键访问对应的节点对象.一个交通运输网络的连通性由弧段类的头节点ID、尾节点ID 与节点类的节点ID的关联实现，即头节点ID 和尾节点ID 为弧段类的外键，节点ID 为节点类的键（Key）.

由于Dijkstra 算法和A∗算法的搜索路径类似于树状结构，且常见交通运输网络基本上呈现稀疏图的特征，生成的二叉树基本上是一棵完全二叉树，可以保证操作不会形成O(N)的最坏结果.另外，在算法实现过程中频繁使用最小数据的取出、已查询数据的删除、重排序等操作，因此采用二叉堆索引来实现交通运输网络的索引是最佳方式.二叉堆的基本元素为弧段，弧段对象的权重为二叉堆的排序因子.

在图3所示的交通运输网络数据结构中，二叉堆采用C++ 标准模板库STL 的Vector 类实现.该二叉堆为小根堆，这意味着位于堆根节点的弧段对象的权重值最小，且堆中每一个位于父节点位置的弧段对象的权重值都小于位于子节点位置的弧段对象的权重值.根据算法需要，该二叉堆的基本操作包括：弧段对象的插入、上移、下移、弹出等.基本操作的时间复杂度在O(1)到O(lnN)之间.弧段对象的插入包括以下步骤：

步骤1将弧段对象压入二叉堆；

步骤2将堆尾的弧段上移至正确的位置.

在上移的过程中，将插入的弧段对象从下到上依次与堆内的各父节点位置的弧段进行比较.若插入的弧段对象的权重小于当前父节点位置的弧段的权重，则两者交换位置；
反之，退出上移过程.弧段对象的弹出过程分为以下步骤：

步骤1将二叉堆头部的弧段对象取出；

步骤2将尾部的弧段对象放至堆头并弹出堆尾；

步骤3将堆头的弧段对象下移至正确位置.

下移的过程跟上移的过程相反.

图3 二叉堆交通运输网络数据结构Figure 3 Binary heap data structure of transportation network

1.3 基于二叉堆的Dijkstra 改进算法

在1.2 节提及的数据结构基础上，本文首先对Dijkstra 算法进行改进，包括以下2 个优化策略：

策略1采用二叉堆的索引结构提高弧段查询效率.

策略2按Double-Float-int 的顺序简化数据类型，从而降低计算耗时.

在二叉堆索引结构下对Dijkstra 算法的改进即优化策略1 的实现如图4所示.算法围绕弧段构建二叉小根堆，依次弹出二叉堆内的弧段，再通过弹出的当前弧段，取出当前弧段所指向节点的所有出向弧段，依次计算每个出向弧段的新的总权重值.若新的总权重值小于出向弧段的原总权重值，则更新该出向弧段的总权重值，并将该出向弧段插入到二叉堆；
若新的总权重值大于等于出向弧段的原总权重值，则继续处理下一个出向弧段.当前弧段的出向弧段处理完成后，算法返回并弹出二叉堆里的下一个弧段，再重复上述过程，直至遇到目标节点或二叉堆为空.算法的最终步骤是沿目标节点反向回溯得到从起始节点到目标节点的最短路径.在算法处理二叉堆弹出的每个弧段过程中，必须避开禁行弧段和禁行转向，禁行弧段和禁行转向即为交通运输网络G中定义的R1和R2约束条件.禁行弧段为不可通行的弧段，如现实交通运输网络中不可通行的路段.禁行转向由多个弧段组成，如现实交通运输网络中禁止左转、禁止掉头等交通策略.

在Dijkstra 算法中，优化策略2 的实现对应图4中“计算出向弧段i的总权重值”，采用可容忍误差将弧段数组中所有弧段的权重值从Double 或Float 数据类型转换为int 值，可以提高计算速度.

1.4 基于二叉堆的A∗改进算法

A∗算法包括以下优化策略：

策略1采用二叉堆的索引结构提高弧段查询效率.

图4 基于二叉堆的Dijkstra 算法Figure 4 Dijkstra algorithm based on binary heap

策略2按Double-Float-int的顺序简化数据类型，从而降低计算耗时.

策略3按开平方根-乘除-加减的顺序简化运算类型，从而降低计算耗时.

策略4减少搜索空间.

在A∗算法的改进过程中，优化策略1 的实现与Dijkstra 算法的过程相同，即图4所示的算法过程.采用二叉堆的索引结构可以比采用其他数据结构更高效地获取当前弧段的下一个连接弧段.优化策略2 和3 的实现步骤对应图4的“计算出向弧段i的新的总权重值”.在A∗算法中，出向弧段i的新的总权重值的计算不同于Dijkstra 算法中的计算方式.在Dijkstra 算法中，出向弧段i的新的总权重值等于当前弧段的总权重值与出向弧段自身的权重值之和；
在A∗算法中，出向弧段i的新的总权重值等于当前弧段的总权重值、出向弧段自身的权重值、当前节点到目标节点的距离估算Dj→t之和，其中Dj→t的公式为

式中，(xt,yt)为目标节点坐标，(xj,yj)为当前节点坐标，Dj→t为目标节点与当前节点之间的欧氏距离.

在实际计算中，由于欧氏距离运用了2 次平方和1 次开平方根计算，计算耗时较大，此外Dj→t只是一个估算值，只需大致接近当前节点j到目标节点t的实际计算值即可.因此，本文采用的距离估算公式为

至此可以实现优化策略3.另外在基本数据中，采用可容忍误差将节点数组的坐标值及弧段数组中所有弧段的权重值从Double 或Float 数据类型有损转换为int 值，从而实现了优化策略2.同时，由于距离估算Dj→t的存在，在算法实现搜索运算的过程中会沿着当前节点j到目标节点t的方向快速前进，有效地减少了搜索空间，从而实现了策略4.

2.1 实验环境及数据

根据以上思路，本文采用Visual C++分别实现了Dijkstra 算法和A∗算法的改进.算法的实现环境如下：实验数据为全国道路交通骨干网以及上海市道路交通网共59 507 个节点、163 099 个弧段，运行硬件环境为CPU 2.3 GHz 主频、4G 内存、120 GB 硬盘.

分析数据内容可知，每个节点实体的平均出度为163 099÷59 507≈2.74，数据呈现稀疏图的特征，形成的二叉树基本相当于一棵完全二叉树.由于出度略大于2，二叉树的深度lnN比较合适，采用二叉堆来实现数据索引可以最大化其搜索效率.实验采用了4 组大范围的最短路径搜索例子，与组内起终点位置相同.每组的第1 个实验采用传统的FIFO 队列实现Dijkstra算法，并将其作为比较基准；
其他3 个实验都采用二叉堆索引实现算法.A∗算法采用了两种距离估计函数，D1代表采用的距离估计函数为式(3)；
D2代表算法所采用的距离估计函数为式(4).

2.2 实验结果与分析

从数据结果观察，同样是Dijkstra 算法，采用二叉堆的数据索引结构与采用传统FIFO 队列的数据结构相比，算法的耗时有明显减少，这证明了优化策略1 是有效的.在A∗算法的应用中，采用D1函数与D2函数相比，搜索空间有显著减少，耗时明显降低.由此可得到两个结论：1）在A∗算法中，选择合适的距离估计函数可以显著减少算法的搜索空间，明显降低算法耗时，这证明优化策略4 是有效的；
2）D1函数采用了开平方根的复杂计算，从而增加了算法的耗时，且其增加的时间超过了因搜索空间减少而减少的计算时间，这也从侧面证明了简化数据类型和操作类型的优化策略2 和3 是有效的.

表2 Dijkstra 算法和A∗算法改进的实验结果Table 2 Results of improvement for Dijkstra and A∗algorithms

图5为部分计算结果地图显示.

图5 部分实验结果地图显示Figure 5 Map display of experimental results

本文针对交通运输网络设计了二叉堆索引结构，并在此基础上实现了计算最短路径的Dijkstra 算法和A∗算法，在算法的实现过程中采用了多种优化策略.首先，通过二叉堆索引的应用提高了交通运输网络存储结构中点线及其网络拓扑关系的查询效率.其次，将点线坐标进行了低精度损耗的数据类型简化，提高了算法计算效率.此外，对A∗算法中当前节点到目标节点的距离估计函数进行了计算方式的优化，有效降低了搜索空间，从而提高了两种算法的整体计算效率.最后，通过编程实现了二叉堆索引结构和算法的优化策略，并随机抽取了多组实验.实现结果显示，对Dijkstra 算法改进后的计算速度提高了7 倍以上，对A∗算法改进后的计算速度提高了200 倍以上，从而证明了本文的改进和优化策略确实达到了预期效果.