作为图论的经典问题, 最短路径在诸多领域都有着广泛的应用, 如:智能交通系统^[1]、地理信息系统^[2-4]、计算机网络与通讯^[5]等.为提升算法的计算效率或满足特定的应用需求, 已有大量优秀算法^[6-8]被提出.按照解的精度, 最短路径算法可分为精确和近似算法; 按照求解目标的数量, 最短路径问题又可分为单源和全(多)源最短路径.本文的研究对象是精确全源最短路径问题, 即旨在求解所有点对之间的精确最短路径.

目前, 求解全源最短路径问题的典型算法包括Floyd算法^[9]和多次Dijkstra算法^[10].其中, Floyd算法的时间复杂度为O(n³); Dijkstra算法是单源最短路径算法, 其时间复杂度为O(n²).为获得全源最短路径, 需执行n次, 故总复杂度为O(n³).由此可见, 全源最短路径算法的时间复杂度依然很高, 难以满足现有大规模网络或实时计算的要求.为进一步提升算法的计算效率, 除设计低复杂度的高效算法外, 还有学者^[11]采用并行计算技术来加速全源最短路径问题的求解, 但并行计算不能减少总的计算量.

重优化方法的基本思想是充分利用异源最短路径树间的相关性, 避免重复计算, 从而达到高效求解全源最短路径的目的.该方法是在已有最短路径树的基础上, 针对网络的动态变化而对路径进行重新调整的过程.目前, 其已被用于解决动态最短路径问题, 如单边权重变化、多边权重变化^[12], 以及源点变化^[13]等情景.由于仅计算最短路径可能发生变化的节点, 故重优化方法能有效减小搜索空间, 提升求解速度.其中, 确定最小搜索空间以及分析最短路径的变化规律是重优化方法的两个重要内容.本文首先分析源点发生变化时, 异源最短路径树间的相关性与差异性, 并依此设计高效的转换方法; 随后将该方法扩展至全源最短路径问题的求解.

将现实网络抽象成无向图G(V, E, W), 其中V为节点集合, E为边集合, W为权重集合, n=|V|为节点数量, m=|E|为边数量.对任意一条边(i, j) ∈E, i∈V, j∈V分别为边(i, j)的两个端点, w(i, j)∈W表示网络边(i, j)的权重.单源最短路径问题是求解从起始点s(或所有点)到终点t具有最小总权重的最短路径.全源最短路径则是求解所有点对间的最短路径.通常, 赋予每个节点i一对标号(d_i, p_i), 其中d_i表示i到t的最短距离, p_i表示最短路径上i的前驱节点, d(i, j)表示节点i和j间的距离.

Dijkstra算法是求解单源最短路径最常用的方法, 其主要步骤包括:1) 将V分解成S和T, 设置S={s}, T=V-S, d_s=0, d_i=∞, ∀i∈V/s; 2) 搜索T中距离S最近的节点j, 计算d_j; 3) 设置S=S∪{j}, T=T-{j}; 4) 若T=∅或t∈S, 算法终止; 否则转至步骤2).

Floyd算法是一种动态规划算法, 适用于求解全源最短路径, 主要步骤包括:1) 初始化任意点对(i, j)间的距离, d(i, j)=w(i, j); 若(i, j)∉E, 则d(i, j)=∞; 2) 对任意点对(u, v), 检查是否存在节点x使得d(u, x)+d(x, v) < d(u, v), 若存在则设置d(u, v)=d(u, x)+d(x, v); 3) 重复步骤2) 至所有点对间的距离都满足最优条件.

当Dijkstra算法计算出网络所有节点到目的节点t的最短路径后, 可生成一棵最短路径树(见图 1a).对于相邻的目的节点t₁和t₂, 其对应的两棵异源最短路径树T(t₁)和T(t₂)存在着很大的相关性.本文以图 1为例, 分析两棵异源最短路径树间的相关性与差异性.

图 1(Fig. 1)

图 1 异源最短路径树实例 Fig.1 An example of the shortest path tree with different sources (a)—原始网络；(b)—最短路径树T(v10); (c)—最短路径树T(v7).

如图 1b所示, T(v₁₀)包含3棵子树:T′(v₇)，T′(v₈)和T′(v₉).为方便表达, T(v₇)表示图 1b中以v₇为根节点的子树, T′(v₇)则为图 1c中以v₇为根节点的最短路径树.对任意节点i, d_i表示在T(v₁₀)中i到v₁₀的最短距离, 而d′_i则表示在T′(v₇)中i到v₇的最短距离, d(i, j)表示节点i与j间的最短距离.对比图 1b和图 1c可知:

1) 子树T′(v₇)的结构保持不变, 但其上所有点的最短距离全部减少2.

证明  对于任意节点i∈T′(v₇), d_i=d(i, v₁₀)=d(i, v₇)+d(v₇, v₁₀), 而d′_i=d(i, v₇)=d_i-d(v₇, v₁₀).由于d(v₇, v₁₀)是全局最短距离, 为固定常量, 故T′(v₇)上所有点的最短距离都减少d(v₇, v₁₀)=2, 结构保持不变.

2) 对任意节点j∈T(v₁₀)-T′(v₇), 都存在|d′_j-d_j|≤d(v₇, v₁₀).

证明  在T(v₇)中, 必存在一条路径P(j, v7)=P(j, v₁₀)+P(v₁₀, v₇).而在T′(v₇)中, 必有d′_j=d(j, v₇) ≤d(j, v₁₀)+d(v₁₀, v₇), 故d′_j-d_j≤d(v₁₀, v₇).因d(v₁₀, v₇)=d(v₇, v₁₀), 所以|d′_j-d_j|≤d(v₇, v₁₀).

由上可知, 当将T(v₁₀)转换至T′(v₇)时, 若更改v₁₀的前驱节点为v₇, 并将T(v₁₀)-T′(v₇)内任意节点i的距离增加d(v₇, v₁₀), 即d_i=d_i+d(v₇, v₁₀), 因d_i-d′_i≤2×d(v₇, v₁₀), 因此i的最短距离变化量在后续计算中不超过2×d(v₇, v₁₀).此外, 若j的最短距离减少Δ, T(v_j)中任意点的最短距离至少减少Δ.

图 2描述了交通网络的一棵最短路径树及异源最短路径树间的差异.图 2a为原始底层交通网络, 共包含1725962个节点, 2864827条边; 在图 2b的最短路径树中, 每个节点(除目的节点A外)都有且仅有一条边连接前驱节点, 故共有1725960条边; 而在图 2c中, 两棵异源(即T(A)和T(B))最短路径树间的差异很小, 仅有1428个节点的前驱节点发生变化.因此, 若仅计算前驱节点发生变化的节点, 则可大幅度降低计算复杂度.

图 2(Fig. 2)

图 2 交通网络下的异源最短路径树 Fig.2 Shortest path tree for real transportation network (a)—原始底层网络；(b)—以A为目的节点的最短路径树; (c)—A源和B源最短路径树差异.

在实现异源最短路径树间的高效转换之前, 需通过Dijsktra等算法求解一棵单源最短路径树T(t₁), 再执行以下步骤将T(t₁)转换成T(t₂).

1) 修改路径P(t₂, t₁)上所有节点的前驱节点, 即若i∈P(t₂, t₁), i≠ t₁, 令j=p_i, 则p_j=i;

2) 修改路径P(t₁, t₂)上所有节点的距离, 即若i∈P(t₁, t₂), 令Δ=2×(d_t2-d_i), 则d_i =Δ+ d_i, 对任意节点k∈T(i), 设置d_k =Δ+ d_k;

3) 将节点集合V分解成S，T和T₁, 初始S={T(t₂)}, T=∅, T₁=V-T-S; 将路径P(t₁, t₂)上的节点依次插入队列Q′队首;

4) 取出Q′队首节点q, 令T={T(q)}, T₁=V-T-S; 将S和T间所有代价差c_ef < 0的边插入到集合Q中, 其中c_ef=w_ef+d_f-d_e, (e, f) ∈E, e∈T, f∈S.

5) 从Q中选择代价差最小的边(u, v), 并从Q中剔除(u, v), 其中c_ef < 0, 设置p_u=v, S=S∪T(u), T=T-T(u), 对任意i∈T(u), d_i=d_i+c_uv;

6) 将T(u)与T间所有代价差c_ef < 0的边插入Q中, 即(e, f)∈E, e∈T, f∈T(u)；

7) 重复步骤5) 和步骤6), 直至Q为空；

8) S=S+T, 若Q′非空, 则转至步骤4), 否则结束.

RASP算法利用上述转换方法, 从已知最短路径树开始, 依次求解网络所有节点的最短路径树, 从而获得全源最短路径.主要包括以下步骤:

1) 初始化所有节点为未访问节点, 随机选择节点t₁作为目的节点, 令t=t₁, 利用Dijsktra算法求解单源最短路径及T(t), 标记t为已访问节点;

2) 使用搜索算法(如广度优先搜索算法)从根节点开始搜索下一个未访问节点t′, 利用异源最短路径树转换方法将T(t)转换成T(t′), 标记t′为已访问节点, 并令t= t′;

3) 重复步骤2) 至所有节点都为已访问节点.

由第2节分析可知, t与t′间的最短距离直接影响异源最短路径树的转换效率, 即距离越近, 效率越高, 因此RASP算法优先选择距离t较近的未访问节点t′; 此外, 集合T+T₁包含的节点越少, 则搜索空间越小, 转换效率越高, 故RASP算法优先选择具有较少子孙节点的t′.

由Dijsktra算法计算得到的初始单源最短路径树是精确解, 故本文只需验证异源最短路径树转换方法的正确性即可确保RASP算法的正确性.证明如下:

1) 在T(t₁)转换成T(t₂)之前, 在网络中添加虚拟节点t₁及虚拟边(t₂, t₀), 其中w(t₂, t₀)=d(t₂, t₁).当更新路径P(t₂, t₁)和距离, 即完成步骤1) 和步骤2) 后, 任意节点都存在唯一路径至t₀, 且其当前记录距离即为该路径长度.后续步骤的目的是调整所有节点的当前路径为到达t₀的最短路径.

2) 步骤3) 将节点集合V分解成S, T和T₁三部分.其中S为已获得最短路径的节点集合, T为待优化的节点集合, 而T₁则是未优化的节点集合.初始时, S={T(t₂)}, 第2节已证明S的结构不会发生变化, 即S内所有节点的当前路径即为最短路径; 在步骤5)~步骤7) 中, 若T能将其内节点的路径优化成最短路径, 则S=S+T内的节点都已获得最优解; 经过步骤4)~步骤8) 后, S=V.以下证明集合T内的节点执行步骤5)~步骤7) 后获得最短路径.

3) 在当前生成树中, 边(u, v)的代价差c_uv=|P(v, t₀)|+w(u, v)-|P(u, t₀)|, c_uv < 0表示路径P(u, v)+P(v, t₀)比当前路径P(u, t₀)更短, 需调整以获得更短路径.若网络中所有边的代价差都为非负值, 则所有节点都已获得最短路径.对于边(u, v), u∈T, 在转换之前满足c_uv=d_v+w_uv-d_u≥0.在最短路径树转换过程时执行步骤1) 和步骤2), 则d_u=d_u+Δ₁, d_v=d_v+Δ₂.若v∈T, 则Δ₁=Δ₂, c_uv≥0;若v∈T₁, 则Δ₁ < Δ₂, c_uv≥0;若v∈S, 则Δ₁ > Δ₂, c_uv可能小于零.因此, 若c_uv < 0, 则必有v∈S.令Δ₃=c_uv < 0为最小的代价差, 则对于任意边(i, j)(u∈T(u), j∈S)的代价差c_ij=c_ij-Δ₃ > 0, 故T(u)中不存在代价差为负值的边, 且其上所有点的最短距离都减少|Δ₃|; 在后续计算中, 集合T-T(u)中的节点距离减少量|Δ₄| < |Δ₃|, 故也不存在c_ij < 0的边(i, j)(i∈T(u), j∈T-T(u)).综上, 执行步骤5)~步骤7) 后, S=S+T, T=∅, S内部不存在代价差为负值的边, 即集合T经过步骤5)~步骤7) 后所有节点都获得最短路径.

异源最短路径树转换方法主要经历以下过程:1) 更改路径P(t₂, t₁)上节点的前驱节点和距离(步骤1) 和步骤2)), 遍历整条路径, 其时间复杂度为O(n₁)，其中n₁为P(t₂, t₁)的长度; 2) 步骤4)~步骤7) 首先搜索S与T间所有的边, 并计算其代价差, 其时间复杂度为O(m₁), 其中m₁为S与T相连边的数量; 然后步骤6) 搜索T(v)与T间所有的边, 时间复杂度为O(m₂), 其中m₂为S与T(u)相连边的数量, 因T(u)的总量为T, 故O(∑m₂)=O(m₁); 3) 在步骤3)~步骤8) 中, T的目的是将集合V-S转移到S, 即∑T=V-S.因此, 异源最短路径树转换方法的时间复杂度为O(n₁+2×∑ m₁)≤O(n+2m).

RASP算法首先执行一次Dijkstra算法以获得初始最短路径树, 其时间复杂度为O(n²); 然后共执行n次异源最短路径树转换方法得到全源最短路径, 其中利用广度(或深度)优先搜索获得下一目的节点, 因此, 异源最短路径树转换的时间复杂度为O(n×(n+(n+2m)))=O(2(n²+nm)).综上所述, RASP算法的时间复杂度为O(n²+2(n²+nm))=O(3n²+2nm).

为测试RASP算法的正确性和时间效率, 本实验基于Window 7操作系统, 采用Visual C++编程, 在CPU为Intel(R) Xeon(R) E5-265 @2.00GHz, 内存为48GB的图形工作站上, 分别利用现实交通网络和人造网络对本算法进行测试, 并与以下4种算法进行对比.① n-Dijkstra-priority(NDP)算法:Dijkstra算法^[10]是经典的求解单源最短路径算法, 根据采用的数据结构不同, 可有多种实现方式, NDP算法采用优先队列, 并执行n次以获得全源最短路径; ② n-Dijkstra-binary(NDB)算法^[14]:不同于NDP算法, NDB算法采用二叉树结构, 并使用二分排序法对候选节点进行排序, 每次迭代中选择标记最小的节点; ③ Floyd算法:Floyd算法^[9]是经典的求解全源最短路径算法, 在稠密网络中能取得较好的计算效率; ④ improved-Floyd(Ⅰ-Floyd)算法:改进的Floyd算法在时间效率上具有一定的优势.

在测试实验中, 本文RASP算法获得网络中任意点对间的最短距离, 与4种对比算法计算所得的最短路径值相同, 验证RASP算法的正确性.在时间效率方面, 测试结果如下.

测试数据集为全国道路网, 共含多个级别的道路, 根据包含道路级别数的不同, 将道路网分成5个大小不同的测试网络:① 网络1包含689155个节点, 1160466条边; ② 网络2包含411719个节点, 946974条边; ③ 网络3包含268326个节点, 349008条边; ④ 网络4包含115122个节点, 149360条边; ⑤ 网络5包含5983个节点, 7468条边.此处定义平均度为边与点的数量之比.表 1为最短路径算法的时间效率对比.

表 1(Table 1)

表 1 最短路径算法时间效率对比 Table 1 Time performance comparison of shortest path algorithms s 算法 网络1 网络2 网络3 网络4 网络5 NDP 75594 27623 10759 1829 0.624 NDB - 98139 38303 5413 0.813 Floyd × × × × 312 Ⅰ-Floyd × × × × 73 RASP 49339 16362 5032 593 0.0912

表 1 最短路径算法时间效率对比 Table 1 Time performance comparison of shortest path algorithms

对比表 1(其中“×”表示超出内存, 无法获得计算时间; “-”表示计算时间过长)中5种算法的测试结果, 可得出以下结论:

1) RASP算法的运行时间仅为NDP的32%~65%, 为NDB算法的12%左右.其原因在于RASP算法仅搜索最短路径可能发生变化的节点, 即集合T+T₁, 故相比于NDP和NDB算法, 大大减少了搜索空间, 提升了计算速度.可见RASP算法在大规模交通网络上, 具有一定的时间优势.

2) 与Floyd和Ⅰ-Floyd算法相比, RASP, NDP和NDB算法在空间复杂度上具有绝对优势, 因为RASP, NDP和NDB算法使用邻接链表(空间复杂度为O(n+m)), 而Floyd和Ⅰ-Floyd算法使用邻接矩阵(空间复杂度为O(n²)), 由于网络1~网络4的数据量较大, Floyd和Ⅰ-Floyd算法无法申请到足够的连续内存, 导致其无法运行.在时间效率上, RASP，NDP和NDB算法也优于Floyd和Ⅰ-Floyd算法.本例测试的交通网络是稀疏网络(平均度为1.7), Floyd和Ⅰ-Floyd算法效率低下.

综上所述, 在交通网络上, RASP算法无论是时间复杂度还是空间复杂度都优于Floyd和Ⅰ-Floyd算法.对比于NDP和NDB算法, RASP算法的运行速度是其运行时间的1.5倍之余.

为进一步测试网络特征对算法的影响, 本实验采用由the first DIMACS workshop^[15]提供的netgen网络生成器, 构建节点数为10000, 平均度分别为8, 16, 32, 64, 128和256的虚拟网络.

由图 3测试结果可知:① Floyd算法受网络平均度的影响很小, 运行时间保持在1750s左右; RASP算法的计算时间随着平均度的增加而呈现递增的趋势, 但总体效率明显优于Floyd算法; ② NDP算法随着平均度的增加, 其运行时间增长速度比RASP算法快, 效率不如RASP算法; ③ NDB和Ⅰ-Floyd算法在本例测试中, 不具备效率优势; ④ RASP算法较其他所有对比算法始终保持最佳的时间效率.

图 3(Fig. 3)

图 3 算法在不同平均度网络中的时间效率对比 Fig.3 Time performance comparison in networks with varying degree

由此可见, 无论是稀疏网络还是稠密网络, RASP算法的时间效率都具有明显的优势.

本文基于重优化理论实现了异源最短路径树间的高效转换, 并在此基础上提出了一种适用于大规模网络的全源精确最短路径求解方法——RASP算法.理论证明该算法的时间复杂度为O(3n²+2nm).实验结果表明:在稀疏的交通网络上, RASP算法的运行时间约为NDP算法的32%~65%, 为NDB算法的12%左右, 明显优于Floyd和Ⅰ-Floyd算法; 在平均度变化的人造网络上, RASP算法的运行效率高于NDP, NDB, Floyd和Ⅰ-Floyd算法.因n < m < n², RASP算法不仅理论时间复杂度在稀疏网络上低, 而且在实际测试中, RASP算法无论是在稀疏还是稠密网络上, 都能取得较好的时间效率, 为快速求解大规模网络的全源最短路径提供了新方法.