基于学习预测的最小两条节点不相交路径算法研究

Accelerating Two Minimum Disjoint Paths Algorithm with Learned Predictions

摘要: 在任意两个节点之间寻找多条节点不相交路径，是提升网络可靠性的基础任务。Suurballe算法为该问题提供了最优解，但该算法依赖重复的最短路径搜索，导致在大规模网络中计算成本高昂。本文提出一种新颖的预测式加速方法。我们引入一种双阶段策略(预测阶段和训练阶段)：预测阶段通过在反向图上进行双向搜索构建监督数据集，用于预测最优解的上界；训练阶段则通过使用并动态更新最优解的预测范围来剪枝搜索空间。该方法将预测机制与双向搜索整合至Suurballe型框架中，同时保证解的最优性。我们从理论上分析证明了算法的加速效果，并针对节点不相交路径问题设计了专用特征提取的方法与搜索协同策略。该框架为大规模网络中的高效多路径优化提供了新的方法论基础。

Abstract: Finding multiple node-disjoint paths is a fundamental task for enhancing reliability in networks. While Suurballe’s algorithm provleadan optimal solution for two such paths, its reliance on repeated shortest-path searches leads to high computational cost in large-scale networks. This paper proposes a novel prediction-guided acceleration approach. A hybrid two-phase strategy is introduced: in an offline learning phase, bidirectional search on a transformed graph collects dynamic search-state features to build a supervised dataset; during online inference, a lightweight trained model prunes the search space by predicting final path lengths from early-stage states. The method integrates prediction and bidirectional search into a Suurballe-type framework while preserving optimality guarantees. Theoretical analysis under a partial random model demonstrates the acceleration effect, and dedicated feature extraction and search coordination strategies are designed for the node-disjoint path problem. The proposed framework offers a new methodological foundation for efficient multi-path optimization in large-scale networks.

1. 引言

在通信网络、数据中心互联以及分布式计算系统中，确保关键节点对之间的可靠传输路径是一项基础且具有挑战性的任务。路径冗余[1]-[3]是一种被广泛采用的核心容错机制，它在同一源节点和目标节点之间建立多条逻辑上独立的传输路径。当某条路径因节点故障或网络拥塞而失效时，流量可以无缝切换到备用路径，从而维持服务的连续性。在此背景下，寻找多条除共同的起点和终点外不共享中间节点的节点不相交路径，已成为网络设计与优化的经典问题[4] [5]。其中，寻找总长度最小的两条节点不相交路径是最常见且最具代表性的场景，它不仅能直接服务于双路径保护和负载均衡，也是理解更一般多路径问题的基础。

对于最小成本节点不相交路径问题，Suurballe于1974年提出了一个标志性的算法[6]。该算法以优雅而高效的方式解决问题：首先找到一条从源到目标的单条最短路径，然后构造一个巧妙的辅助图(即转换图)，并在其中寻找一条新的最短路径。这条新路径通过一种称为“交替”的操作与原路径结合，最终得到一对总长度最小的节点不相交路径。Suurballe算法的理论完备性和实际有效性使其在数十年来成为该领域的标准解决方案[7]。然而，随着现代网络规模的迅速扩张，其固有的计算开销日益凸显。核心瓶颈在于，该算法需要在辅助图上进行一次完整的最短路径搜索，其时间复杂度与标准的Dijkstra算法相同。即使采用理论上最优的优先队列实现[8]，对于大型图或需要频繁进行路径计算的动态网络环境，其开销可能变得难以承受。

传统的加速方法，如双向搜索[9]和启发式剪枝[10]，在特定场景下可以提高效率，但往往缺乏理论保证或普适性[11]。新兴的“带预测的算法”范式为这一问题提供了新的视角[12]-[14]。该范式允许算法利用机器学习提供的预测来指导搜索过程，在预测准确时获得远超传统算法的性能，同时在预测错误时仍能保证基本的最坏情况性能。然而，现有的预测增强算法主要关注单源节点与目标节点集之间的最短路径问题[15]，尚无专门针对节点不相交路径问题定制的预测增强方案。类似地，尽管学习增强方法已在匹配等其他组合优化问题中展现出潜力[16]，但其在多路径路由中的应用仍待探索。

近年来，机器学习和预测机制已被引入经典算法的设计中以提升其效率。Feijen和Schäfer提出的“带预测的Dijkstra”算法[15]即为一例。该算法利用早期迭代中的路径特征来预测最终的最短路径长度，并基于此预测修剪不必要的边，从而减少优先队列操作次数。实验表明，该算法在随机图模型中显著降低了计算开销。同时，双向搜索作为一种经典的启发式策略[9]，已广泛应用于单源单目标最短路径问题。针对多目标场景的类似启发式方法也已被探索[17]，大幅缩小了搜索范围并提升了算法效率。

如何将学习增强方法的高效性与Suurballe算法求解节点不相交路径的框架进行深度融合，仍然是一个开放性问题。直接将预测机制应用于Suurballe算法的关键步骤面临独特挑战：辅助图的结构与权重动态地依赖于每次迭代中找到的路径，使得搜索过程的特征更加复杂多变。

因此，本文聚焦于最小两条节点不相交路径这一具体问题，主要贡献如下。

我们提出了一个新颖的框架，将学习增强的预测机制与Suurballe算法相融合，以加速求解总长度最小的两条节点不相交最短路径。在预测阶段，该框架采用双向搜索策略，高效地从源节点和目标节点两个方向收集路径状态数据。与传统的单向搜索相比，此方法在数据获取阶段显著减少了所需搜索空间，同时为预测模型的训练提供了更丰富、更均衡的拓扑特征数据集。在训练阶段，该框架能够早期识别并剪枝无希望的搜索分支。这种预测引导的搜索策略在保持原始Suurballe算法最优性保证的同时，显著提升了整体搜索效率，实现了兼具理论保证的实用加速。我们对所提框架的加速效果进行了理论分析。随后证明，即使是在最坏情况下，算法性能也会退化为经典的Suurballe算法，其时间复杂度仍为$O\left(m+n\log n\right)$ ，其中m表示边数，n表示节点数。该分析为设计具有可证明效率的学习增强路径优化算法提供了理论基础。

后续章节结构安排如下：第2章回顾必要的理论背景，涵盖Suurballe算法的关键步骤、双向搜索策略以及学习增强算法的基本原理。第3章详述我们提出的双阶段框架，包括训练阶段的双向搜索数据收集、预测模型设计以及应用阶段集成的预测搜索流程。第4章对所提方法的时间复杂度和加速效果进行理论分析。最后，第5章总结全文并提出未来研究方向。

2. 问题描述与分析

给定一个带权有向图$G=\left(V,E\right)$ ，其中$V$ 是节点集，$\left|V\right|=n$ ；$E$ 是边集，$\left|E\right|=m$ ；每条边$e\in E$ 具有非负权重$w\left(e\right)\in {ℝ}_{\ge 0}$ 。设源节点为$s\in V$ ，目标节点为$t\in V$ 。传统的最短路径问题旨在找到一条从$s$ 到$t$ 的路径$P$ ，使得总权重$w\left(P\right)={\displaystyle \sum _{e\in P}w}\left(e\right)$ 最小。本文专注于最小两条节点不相交路径问题。

Table 1. Main symbols and description

表1. 主要符号及解释

符号	解释
S	交错路径
$L_f\left[v\right]$ , $L_b\left[v\right]$	在图$G$ 中从$s$ 到$v$ ($L_f\left[v\right]$ )以及从$t$ 到$v$ ($L_b\left[v\right]$ )的最短距离
$d_f\left(u\right)$ , $d_b\left(u\right)$	节点$u$ 的前向/后向$d$ 值
B	不相交路径对总长度的上界，在搜索过程中更新
P	用于剪枝的交错路径预测长度
$\alpha$ , $\beta$	用于调整预测值$P$ 的膨胀因子
$S_f$ , $S_b$	前向与后向双向搜索中已确定节点的集合

本节详细阐述最小两条节点不相交路径问题的模型与分析，重点在于如何通过引入Suurballe算法、双向搜索及机器学习预测技术来优化路径计算。结合这些方法，我们旨在提高计算第二条路径的效率，尤其是在大规模图结构中。本文使用的主要符号如表1所示。

2.1. 基于预测的最小两条节点不相交路径问题

Suurballe算法是求解节点不相交最短路径对问题的经典算法。其核心思想是构建第一条最短路径，然后利用一条交错路径来构建第二条最短路径，从而确保两条路径互不重叠，参见图1。

(a) (b)

Figure 1. Interlacing path S and paths correction

图1. 交错路S与路径修正

定义2.1 (最小两条节点不相交路径)。给定一个带权图$G=\left(V,E,w\right)$ ，其中$V$ 是顶点集，$E\subseteq V\times V$ 是弧集，$w:E\to {ℝ}_{\ge 0}$ 是非负权重函数。对于指定的源顶点$s\in V$ 和目标顶点$t\in V$ ，最小两条节点不相交路径(2-MNDP)是指从$s$ 到$t$ 的一对节点不相交路径$P_1$ 和$P_2$ ，它们使得总长度$w\left(P_1\right)+w\left(P_2\right)$ 最小，其中$P_1$ 和$P_2$ 除$s$ 和$t$ 外不共享任何顶点。

定义2.1 (交错路径)。给定从源$s$ 到目标$t$ 的两条节点不相交路径$P_1$ 和$P_2$ ，一条交错路径$S$ 是$s$ 和$t$ 之间的一条带符号标记的路径，满足以下条件：

1. $S$ 中属于$P_1$ 或$P_2$ 的每条边都被赋予一个负号。

2. $S$ 中位于$S$ 与$\left\{P_1,P_2\right\}$ 交集上的每个顶点，在$S$ 中必须至少与一条带负号的边相关联。

Suurballe算法的执行过程可以直观地理解为：基于已有路径，通过特定的“修正”操作来构建第二条不相交路径。具体而言，算法首先在图$G$ 中寻找一条从$s$ 到$t$ 的最短路径$P_1$ 。这一步使用标准的Dijkstra算法实现；设$P_1$ 的长度为$L_1$ 。

该算法的关键在于第二步：如何找到另一条与$P_1$ 不共享中间顶点，同时又能最小化$L_1+w\left(P_2\right)$ 的路径$P_2$ 。Suurballe提出了一种基于路径差的构建方法。考虑两条路径$P_1$ 和一条候选路径$P_2$ ，它们的对称差可以表示为一个有向子图，其中$P_2$ 中的边标记为正，$P_1$ 中的边标记为负，而两条路径共享的边相互抵消。这个对称差图包含一条从$s$ 到$t$ 的有向路径，其长度等于$w\left(P_2\right)-w\left(P_1\right)$ 的绝对值。

该算法的计算复杂度主要取决于两个搜索过程：第一个是时间复杂度为$O\left(m+n\log n\right)$ 的标准Dijkstra搜索；第二个是改进的路径搜索。假设使用基于斐波那契堆的Dijkstra算法，每轮最短路径搜索的时间复杂度为$O\left(m+n\log n\right)$ ，其中$m=\left|E\right|$ ，$n=\left|V\right|$ 。因此，寻找$K$ 条路径的总时间复杂度为$O\left(K\left(m+n\log n\right)\right)$ 。

2.2. 双向搜索策略

双向搜索作为图论中的经典算法增强技术，通过从源节点和目标节点同时启动搜索过程，打破了传统单向搜索的固有模式。在Suurballe算法的理论框架内，我们创新性地将该策略引入改进的路径搜索阶段，为求解节点不相交路径这一经典组合优化问题的效率提升开辟了新途径。

双向Dijkstra算法同时从源节点$s$ 和目标节点$t$ 开始搜索，直到两个搜索前沿相遇。设$G=\left(V,E,w\right)$ 为有向加权图，其反向图为$G^{\prime }=\left(V,E^{\prime },w^{\prime }\right)$ ，其中$E^{\prime }=\left\{\left(v,u\right)|\left(u,v\right)\in E\right\}$ ，$w^{\prime }\left(v,u\right)=w\left(u,v\right)$ 。搜索过程维护两个距离标签函数：$d_f:V\to {ℝ}_{\ge 0}\cup \left\{\infty \right\}$ 和$d_b:V\to {ℝ}_{\ge 0}\cup \left\{\infty \right\}$ ，分别表示从$s$ 出发的前向距离估计和从$t$ 出发的后向距离估计。同时还维护两个已确定节点的集合$S_f,S_b\subseteq V$ ，满足以下不变性：

1. 若$v\in S_f$ ，则$d_f\left(v\right)$ 为从$s$ 到$v$ 的最短距离。

2. 若$v\in S_b$ ，则$d_b\left(v\right)$ 为从$v$ 到$t$ (在$G$ 中)的最短距离。

当存在顶点$u\in S_f\cap S_b$ 时，我们称$u$ 为相遇顶点。此时，可以构造出一条长度为$d_f\left(u\right)+d_b\left(u\right)$ 的$s$ -$t$ 路径。特别地，若$u^{*}=\arg {\min }_{u\in S_f\cap S_b}\left[d_f\left(u\right)+d_b\left(u\right)\right]$ ，则对应的路径长度为当前已知最优上界。在结构均匀的图中，双向策略可将计算复杂度降低至单向搜索的约$1/2^{\alpha }$ ，其中指数$\alpha$ 取决于图本身的拓扑特性。此外，双向框架自然地提供了早期剪枝的机会；从搜索两侧获得的中间结果可以相互共享和验证，使得潜在的搜索分支能够被更早地排除。

3. 启发式算法

本节在经典Suurballe算法[6]及近年来学习增强算法进展[15]的启发下，我们提出一个新颖的双阶段框架以加速计算最小两条节点不相交路径。该方法将双向搜索策略与机器学习预测相结合，旨在降低计算开销的同时保持最优性保证。

3.1. 算法框架

我们将通过以下步骤构建最小两条节点不相交路径，这些步骤将使用算法1~5。

步骤1. 我们首先采用算法1，使用Dijkstra算法计算从源节点$s$ 到目标节点$t$ 的第一条最短路径$P_1$ 。令$L_1=w\left(P_1\right)$ 表示其长度。随后，我们在转换图G'上同时从$s$ 和$t$ 执行双向搜索。在此搜索过程中，我们维护并更新每个节点$v$ 的$d$ 值，该值定义为当前路径长度与$L_1$ 的偏差。在每一步中，我们选择具有最小$d$ 值的节点进行扩展，优先选择那些保持接近最优解的路径。

步骤2. 在算法2中，我们对前$i_0$ 次迭代执行双向搜索，始终选择具有最小$d$ 值的节点。后续操作遵循标准的Suurballe流程。当遇到一个节点$u$ 同时出现在前向和后向搜索前沿时，我们获得第二条不相交路径的长度。对于多组源–目标节点对，我们收集训练样本$\left(X,y\right)$ ，其中$X$ 包含记录的$d$ 值以及其他搜索状态特征。随后，我们基于此数据训练回归模型$M$ 。

步骤3. 在预测阶段，我们采用算法3中预测引导的单向搜索。在每一步中，我们提取与训练阶段相同的特征$X$ (尤其是$d$ 值)。查询训练好的模型$M$ 以获得预测的交错路径长度$\widehat{L}$ 。随后，我们使用$\widehat{L}$ 对搜索空间进行剪枝：跳过任何当前路径长度超过$\widehat{L}$ 的节点$v$ 。每一步内的节点探索过程与Suurballe算法保持一致。搜索持续进行，直到找到一条长度接近$\widehat{L}$ 的完整交错路径，或者剪枝后的搜索空间被完全探索。

步骤4. 算法4构成了整个算法的核心松弛操作。对于每个新发现或距离更新的节点，该过程首先判断其距离是否改善了当前记录值。若是，则根据节点距离与预测值$P$ 的关系，将该节点分配至优先队列PQ(若其距离未超过$P$ )或储备集$R$ (若其距离超过$P$ )。对于已位于$R$ 中的节点，若其距离因后续搜索进展而降至$P$ 以下，则将其重新激活并移回PQ。

步骤5. 算法5用于处理初始预测可能不足的情况(例如，搜索完成但未找到有效的交错路径)。它通过将$\widehat{L}$ 乘以系数$\beta >1$ 来动态调整预测，并重新激活被剪枝的节点。当获得第二条节点不相交路径且其总长度位于预测边界内时，算法终止。

3.2. 初始化

该初始化算法为后续的双向搜索预测阶段构建了必要的数学框架与数据结构。由于标准的Dijkstra算法在找到目标节点$t$ 后不会立即停止，而是继续运行直至优先队列为空，从而自然计算出从源节点$s$ 到所有节点的最短距离。这一特性使得我们可以在一次搜索中同时获得$P_1$ 和$L_f[\cdot ]$ 。为此，算法1首先通过两次独立的Dijkstra搜索建立全局距离信息：第一次搜索(第2行)从源节点$s$ 出发，在计算到目标节点$t$ 的最短路径$P_1$ 及其长度$L_1$ 的同时，计算出从$s$ 到图中所有节点$v$ 的最短距离$L_f\left[v\right]$ ；第二次在反向图$G_{\text{rev}}$ 上的搜索(第3行)从$t$ 出发，计算从每个节点$v$ 到$t$ 的最短距离$L_b\left[v\right]$ 。这两个距离数组$L_f$ 和$L_b$ 分别刻画了节点在前向与反向拓扑结构中的可达性代价。

基于最短路径$P_1$ 的结构，算法随后(第6~11行)识别并排除关键节点：若路径$P_1$ 包含至少三个节点($\left|P_1\right|\ge 3$ )，则将$s$ 之后的第一个节点作为$s_1$ ，将$t$ 之前的最后一个节点作为$t_1$ ；否则(在直接连接的特殊情况下)，设$s_1=t$ ，$t_1=s$ 。

算法1 初始化算法

输入：图$G=\left(V,E,w\right)$ ，源节点$s$ ，目标节点$t$ 输出：前向距离$L_f$ ，后向距离$L_b$ ，首尾节点$s_1,t_1$ ，节点集$V_f,V_b$ ，d值$d_f,d_b$ 1: $P_1,L_1,L_f\leftarrow \text{Dijkstra}\left(G,s,t\right)$ 2: $L_b\left[v\right]\leftarrow \text{Dijkstra}\left(G_{\text{rev}},t\right),\forall v\in V$ 3: if $\left|P_1\right|\ge 3$ then4: $s_1\leftarrow v_1$ 5: $t_1\leftarrow v_k$ 6: else7: $s_1\leftarrow t$ 8: $t_1\leftarrow s$ 9: end if10: $V_f\leftarrow V\setminus s,s_1$ 11: $V_b\leftarrow V\setminus t,t_1$ 12: for each $u\in V_f$ then13: if $u\in \partial \left(s\right)$ then14: $d_f\left(u\right)\leftarrow w\left(\left(s,u\right)\right)-L_f\left(u\right)$ 15: else16: $d_f\left(u\right)\leftarrow \infty$ 17: end if18: end for19: for each $u\in V_b$ then20: if $u\in \partial \left(t\right)$ then21: $d_b\left(u\right)\leftarrow w\left(\left(t,u\right)\right)-L_b\left(u\right)$ 22: else23: $d_b\left(u\right)\leftarrow \infty$ 24: end if25: end for

此构造得到两个节点集：前向集(包含除$s$ 和$s_1$ 外的所有节点)；以及后向集$V_b=V\backslash \left\{t,t_1\right\}$ (包含除$t$ 和$t_1$ 外的所有节点)。这$V_f=V\backslash \left\{s,s_1\right\}$ 两个集合定义了后续双向搜索中允许探索的节点范围。最后，算法初始化$V_f$ 和$V_b$ 中节点的$d$ 值(第13~22行)：对于$u\in V_f$ ，若$u$ 是$s$ 的直接邻居，则其前向$d$ 值$d_f\left(u\right)=w\left(\left(s,u\right)\right)-L_f\left(u\right)$ (边权重$w\left(\left(s,u\right)\right)$ 与前向最短距离$L_f\left(u\right)$ 的差值，反映直接边与最短路径的成本偏移)；否则，$d_f\left(u\right)=\infty$ 。类似地，对于$u\in V_b$ ，若$u\in \partial \left(t\right)$ ，则其后向$d$ 值$d_b\left(u\right)=w\left(\left(t,u\right)\right)-L_b\left(u\right)$ ；否则，$d_b\left(u\right)=\infty$ 。这些$d$ 值将在后续搜索中作为启发式信息，引导算法优先探索偏离基线路径$L_1$ 最小的节点。

3.3. 双向搜索

本文提出的算法2实现了一种完全对称的探索策略，在每次迭代中交替进行前向和后向搜索。$L_{f^{\prime }}\left[v\right]$ 和$L_{b^{\prime }}\left[v\right]$ 用于跟踪更新后的距离，$S_f$ 和$S_b$ 则记录每个方向上已处理的节点。搜索最多进行$i_0$ 次迭代，除非更早发现相遇节点，否则每次迭代都执行前向和后向扩展步骤。算法从$V_f$ 中选择具有最小$d_f$ 值的节点$u_f$ ，计算其更新后的前向距离$L_{f^{\prime }}[u_f]=d_f[u_f]+L_f[u_f]$ ，并将其加入前向已处理集合$S_f$ (第13~24行)。

算法2 双向搜索算法

输入：图$G=\left(V,E,w\right)$ ，$s$ ，$t$ ，前向距离$L_f$ ，后向距离$L_b$ ，$d_f,d_b$ ，$V_f,V_b$ ，$s_1,t_1$ ，早期停止迭代次数$i_0$ 输出：记录的特征$X=d,B$ 1: $\forall v\in V$ , $L_{f^{\prime }}\left[v\right]\leftarrow \infty$ , $L_{b^{\prime }}\left[v\right]\leftarrow \infty$ , $L_{f^{\prime }}\left[s\right]\leftarrow 0$ , $L_{b^{\prime }}\left[t\right]\leftarrow 0$ 2: $S_f\leftarrow \varnothing$ , $S_b\leftarrow \varnothing$ , $X\leftarrow \varnothing$ , $i\leftarrow 0$ , $B\leftarrow \infty$ 3: $meetin{g}_{found}\leftarrow \text{false}$ 4: $meetin{g}_{node}\leftarrow \text{null}$ 5: while $i<i_0$ and not $meetin{g}_{found}$ then6: $i\leftarrow i+1$ 7: if $V_f\ne \varnothing$ then8: $u_f\leftarrow \arg {\min }_{v\in V_f}{d}_f\left[v\right]$ 9: $V_f\leftarrow V_f\backslash u_f$ 10: $L_{f^{\prime }}\left[u_f\right]\leftarrow d_f\left[u_f\right]+L_f\left[u_f\right]$ 11: $S_f\leftarrow S_f\cup u_f$ 12: 运行Suurballe算法步骤13: $X.\text{add}\left("前向",u_f,d_f\left[u_f\right]\right)$ 14: if $u_f\in S_b$ then15: $D\leftarrow d_{f^{\prime }}\left[u_f\right]+d_{b^{\prime }}\left[u_f\right]$ 16: $B\leftarrow L_{f^{\prime }}\left[u_f\right]+L_{b^{\prime }}\left[u_f\right]$ 17: $meetin{g}_{found}\leftarrow \text{true}$ 18: $meetin{g}_{node}\leftarrow u_f$ 19: $X.\text{add}\left("前向",u_f,D\right)$ , $X.\text{add}\left("\text{B}值",B\right)$ 20: 跳出循环21: endif22: endif23: if $V_b\ne \varnothing$ and not $meetin{g}_{found}$ then24: $u_b\leftarrow \arg {\min }_{v\in V_b}{d}_b\left[v\right]$ 25: $V_b\leftarrow V_b\setminus u_b$ 26: $L_{b^{\prime }}\left[u_b\right]\leftarrow d_b\left[u_b\right]+L_b\left[u_b\right]$ 27: $S_b\leftarrow S_b\cup u_b$ 28: 运行Suurballe算法步骤29: $X.\text{add}\left("后向",u_b,d_b\left[u_b\right]\right)$ 30: if $u_b\in S_f$ then31: $D\leftarrow d_{f^{\prime }}\left[u_b\right]+d_{b^{\prime }}\left[u_b\right]$ 32: $B\leftarrow L_{f^{\prime }}\left[u_b\right]+L_{b^{\prime }}\left[u_b\right]$ 33: $meetin{g}_{found}\leftarrow \text{true}$ 34: $meetin{g}_{node}\leftarrow u_b$ 35: $X.\text{add}\left("相遇��",u_b,D\right)$ , $X.\text{add}\left("\text{B}值",B\right)$ 36: 跳出循环37: end if38: end if39: end while

随后，它调用Suurballe算法过程，根据当前搜索状态调整边权重并管理路径转换。在处理$u_f$ 之后立即检查相遇条件：如果$u_f$ 已存在于$S_b$ 中，则从前向视角看已经相遇。此时，算法计算$D=d_{f^{\prime }}\left[u_f\right]+d_{b^{\prime }}\left[u_f\right]$ 和完整的交替路径长度$B=L_{f^{\prime }}\left[u_f\right]+L_{b^{\prime }}\left[u_f\right]$ ，将这些值连同相遇节点信息记录到特征集$X$ 中，并终止搜索。

如果在向前阶段未检测到相遇，算法则进入向后阶段：从$V_b$ 中选择具有最小$d_b$ 值的节点$u_b$ ，将其向后距离更新为$L_{b^{\prime }}\left[u_b\right]=d_b\left[u_b\right]+L_b\left[u_b\right]$ ，并将其加入$S_b$ (第26~37行)。应用相同的Suurballe算法\cite{Suurballe1974}过程，并进行对称的相遇检查：如果$u_b$ 已存在于$S_f$ 中，则从后向视角看已经相遇。算法随后计算相应的$D$ 和$B$ 值，记录相遇信息并终止。

3.4. 训练阶段

算法3在给定的图$G$ 、源节点$s$ 与目标节点$t$ 上运行。它首先执行标准的Dijkstra算法以计算第一条最短路径$P_1$ 及其长度$L_1$ 。主要的搜索过程在一个循环中展开，只要优先队列非空且队列中的最小优先级不超过当前预测值$P$ ，该循环就会持续。

在每次迭代中，从队列中提取具有最小距离标签的节点$u$ 。如果$u$ 是目标节点$t$ ，算法将记录发现的路径长度$L_{\text{found}}$ 并跳出循环，这标志着已找到一条从$s$ 到$t$ 的完整路径。在前$i_0$ 次迭代中，算法记录搜索轨迹特征：对于每次迭代，当前节点的距离$d\left(u\right)$ 和当前上界$B$ 作为一个数据对存储在特征数组X[i]中。当迭代计数器恰好达到$i_0$ 时，算法调用预测函数PREDICTION，基于已收集的特征$X$ 生成初始路径长度预测。该值随后乘以膨胀因子$\alpha$ ($\alpha \ge 1$ )以得到正式的预测值$P$ 。

接着，对于当前节点$u$ 的每条出边$\left(u,v\right)$ ，算法计算暂定距离$tent=d\left(u\right)+L\left(u\right)$ 。随后调用Suurballe算法步骤以执行Suurballe算法特有的边权重调整和交错路径构建——这是确保最终找到节点不相交路径的关键步骤，与标准的Suurballe方法保持一致。如果tent超过了当前上界$B$ ，则对该边进行剪枝，因为它无法产生比当前已知最优路径更短的解。如果目标节点$t$ 可通过此边到达，则更新上界：$B=\min \left\{tent,B\right\}$ 。算法随后运行算法4，该算法根据tent与预测值$P$ 的关系，决定节点$v$ 应插入优先队列PQ还是储备集$R$ ：若$tent\le P$ ，则插入PQ；否则，放入$R$ 。在循环结束时，算法5过程处理预测值低估真实路径长度的情况。

搜索结束后，获得真实的最短路径长度$L_{\text{true}}$ 。特征数组$X$ 与此真实长度$y=L_{\text{true}}$ 配对形成训练样本$(X,y)$ ，并添加至训练数据集$D_{\text{train}}$ 。通过对大量不同的图实例和源–目标节点对重复此过程，积累了丰富的训练数据。最后，在完整数据集$D_{\text{train}}$ 上训练回归模型$M$ 。训练好的模型$M$ 随后在预测阶段被部署，以快速估计新实例的交错路径长度，从而实现算法的整体加速。

算法3 训练阶段算法

输入：图$G=\left(V,E,w\right)$ ，源节点$s$ ，目标节点$t$ 输出：训练数据集 $D_{\text{train}}=\left(X_j,y_j\right)$ ，其中$X_j$ 为特征，$y_j$ 为真实最短路径长度 1: $P_1,L_1\leftarrow \text{Dijkstra}\left(G,s,t\right)$ 2: $d\left(s\right)=0$ ，$d\left(v\right)=\infty$ 对于所有$v\in V\backslash s$ 3: $D_{\text{train}}\leftarrow \varnothing$ , $B=\infty$ ，$P=\infty$ ，$X=\left[\right]$ ，$i=0$ 4: $\text{PQ}\text{.INSERT}\left(s,d\left(s\right)\right)$ ，$R=\varnothing$ 5: while PQ.非空() 且 PQ.最小优先级() $\le P$ then6: $u=\text{PQ}\text{.REMOVE-MIN}\left(\right)$ 7: if $u=t$ then8: $L_{\text{found}}=d\left(u\right)$ 9: 跳出循环10: end if11: $i=i+1$ 12: if $i\le i_0$ then13: $X\left[i\right]=\left(d\left(u\right),B\right)$ 14: end if15: if $i=i_0$ then16: $P=\alpha \cdot \text{PREDICTION}\left(X\right)$ 17: end if18: for each $\left(u,v\right)\in E$ then19: $tent=d\left(u\right)+L\left(u\right)$ 20: 运行 Suurballe 算法步骤21: if $tent>B$ then 继续 end if22: if $v=t$ then23: $B=\min tent,B$ 24: end if25: 运行算法426: end for27: 运行算法528: end while29: $y=L_{\text{true}}$ 30: $D_{\text{train}}\leftarrow D_{\text{train}}\cup \left(X,y\right)$ 31: 使用回归方法在 $D_{\text{train}}$ 上训练预测模型 $M$

3.5. RELAX-PREDICTION过程

RELAX-PREDICTION过程是训练算法中的核心松弛操作，它根据暂定距离tent和当前预测值$P$ 动态管理节点的插入与更新策略。当通过边$\left(u,v\right)$ 发现的暂定距离tent改进了节点$v$ 当前记录的距离$d\left(v\right)$ 时，该过程被触发。它更新$v$ 的距离信息并调整其在搜索数据结构中的位置。

首先，将tent与$d\left(v\right)$ 进行比较。若$tent<d\left(v\right)$ ，则执行更新：记录旧距离值$d_{\text{old}}$ ，并将$d\left(v\right)$ 更新为tent。随后根据$v$ 之前的状态采取不同的操作。如果$v$ 是首次被发现($d_{\text{old}}=\infty$ )，则根据tent与预测值$P$ 的关系决定其放置位置。若$tent\le P$ ，则将$v$ 插入优先队列PQ以继续参与当前轮次的搜索；否则，将其插入储备集$R$ 进行暂存。

算法4 RELAX-PREDICTION算法

1: if $tent<d\left(v\right)$ then2: $d_{\text{old}}\leftarrow d\left(v\right)$ 3: $d\left(v\right)\leftarrow tent$ 4: if $d_{\text{old}}=\infty$ then5: if $tent\le P$ then6: $\text{PQ}\text{.INSERT}\left(v,tent\right)$ 7: else8: $R.\text{INSERT}\left(v,tent\right)$ 9: end if10: else11: if $v\notin R$ then12: $\text{PQ}\text{.DECREASE-PRIORITY}\left(v,tent\right)$ 13: else14: if $tent>P$ then15: $R.\text{DECREASE-PRIORITY}\left(v,tent\right)$ 16: else17: $R.\text{REMOVE}\left(v\right)$ 18: $\text{PQ}\text{.INSERT}\left(v,tent\right)$ 19: end if20: end if21: end if22: end if

如果$v$ 是一个已被发现的节点($d_{\text{old}}\ne \infty$ )，则进一步区分其当前位置。当$v$ 不在储备集$R$ 中时，直接调用PQ.DECREASE-PRIORITY来更新其在优先队列中的优先级。如果$v$ 已经在$R$ 中，则根据更新后的tent与$P$ 的关系进行处理：当$tent>P$ 时，仅更新该节点在$R$ 中的优先级；当$tent\le P$ 时，表明该节点已进入预测路径长度范围，则将其从$R$ 中移除并插入PQ，使其能够重新加入主搜索过程。

3.6. UPDATE-PREDICTION过程

UPDATE-PREDICTION过程在优先队列变为空而搜索尚未完成时被调用，这表明当前的预测值$P$ 可能低估了真实路径长度。该过程通过增大预测值并重新激活储备集中符合条件的节点，使搜索得以继续。

算法5 UPDATE-PREDICTION算法

1: $P\leftarrow \beta \cdot P$ 2: for each 节点 $v\in R$ then3: if $d\left(v\right)\le B$ then4: $R.\text{REMOVE}\left(v\right)$ 5: $\text{PQ}\text{.INSERT}\left(v,d\left(v\right)\right)$ 6: end if7: end for

首先，将当前预测值$P$ 乘以一个膨胀因子$\beta$ ($\beta >1$ )，得到一个新的预测值。随后，遍历储备集$R$ 中的所有节点，并检查每个节点$v$ 的距离标签$d\left(v\right)$ 是否满足激活条件：当且仅当$d\left(v\right)\le B$ 时，即节点的当前距离不超过已知的最优上界$B$ ，该节点被认为可能构成更优路径的一部分。满足此条件的节点将从$R$ 中移除，并被插入优先队列PQ，从而重新加入主搜索过程。

3.7. 时间复杂性分析

本文提出的加速Suurballe算法在时间复杂度方面保持了严格的理论保证。

定理1. 在最坏情况下，即预测完全不准确时，该算法退化为经典的Suurballe算法，其时间复杂度保持为$O\left(m+n\log n\right)$ ，其中$m$ 表示边数，$n$ 表示节点数。

证明：当预测值$P$ 完全错误(例如$P=0$ )或预测机制被禁用时，该算法退化为结合了Dijkstra剪枝技术的标准Suurballe算法。此时，第一次Dijkstra搜索计算第一条最短路径$P_1$ 的时间为$O\left(m+n\log n\right)$ 。构建辅助图G'需要遍历所有边，耗时$O\left(m\right)$ 。第二次搜索在G'上执行标准的Dijkstra算法，同样耗时$O\left(m+n\log n\right)$ 。UPDATE-PREDICTION过程最多被调用$O\left(\log W\right)$ 次，其中$W$ 为最大边权重，每次调用处理$O\left(n\right)$ 个节点，总成本为$O\left(n\log W\right)$ 。由于在边权重多项式有界的假设下$\log W=O\left(\log n\right)$ ，因此最坏情况下的总时间复杂度为：

$T_{\text{worst}}=2\cdot O\left(m+n\log n\right)+O\left(m\right)+O\left(n\log n\right)=O\left(m+n\log n\right).$

优先队列的斐波那契堆实现支持每次Dijkstra搜索在$O\left(m+n\log n\right)$ 时间内完成[18]，而Suurballe算法需要进行两次这样的搜索。尽管UPDATE-PREDICTION过程可能引入额外开销，但储备集$R$ 的大小永远不会超过节点总数$n$ ，且每次更新的成本可被限定为$O\left(\left|R\right|\right)$ 。综合这些因素，该算法保持了与经典Suurballe算法相同的最坏情况时间复杂度$O\left(m+n\log n\right)$ 。

4. 理论分析

本节提供关于解最优性的理论证明。Suurballe算法作为最小和节点不相交路径问题的经典精确解，自1974年以来其正确性已被严格证明。我们所引入的预测加速机制，本质上是将一种基于机器学习预测的智能剪枝策略整合到了Suurballe算法的搜索过程中。为分析该策略在随机网络拓扑下的预期性能，我们采用经典的随机图模型[19]来描述图的生成分布，并在此基础上讨论算法的期望加速效果。

4.1. 算法的最优性保证

令源节点为$s\in V$ ，目标节点为$t\in V$ ，图$G=\left(V,E,w\right)$ 的边权重函数为$w:E\to {ℝ}_{\ge 0}$ 。记$P_1^{*},P_2^{*}$ 为总权重最小的节点不相交路径对，其目标函数值为：

其中表示所有$s$ -$t$ 节点不相交路径对的集合。

该算法使用一个预测值$P$ 来指导搜索，该预测值满足条件$P\ge D$ ，其中$D=w\left(P_1^{*}\right)+w\left(P_2^{*}\right)-w\left(P_1\right)$ 是第二条路径的可能最小长度(第一条路径$P_1$ 已通过标准Dijkstra预先计算)。令$\alpha$ 为膨胀因子；实际使用的预测边界为$P^{\prime }=\alpha \cdot P$ 。对于任何边$\left(u,v\right)\in E$ ，其暂定距离$tent\left(u,v\right)=d\left(u\right)+w\left(u,v\right)$ 在满足以下条件时被剪枝：

$tent\left(u,v\right)>\min \left\{B,P^{\prime }\right\},$

其中$B$ 是当前最佳上界。由$P^{\prime }\ge D$ 可知，满足$tent\left(u,v\right)\le D$ 的边将不会被剪枝，并且$P_1^{*}$ 和$P_2^{*}$ 上的所有边均满足此条件(根据Suurballe算法的构建原理)。因此，该算法保证在有限步内找到最优路径对：

$\underset{k\to \infty }{\lim }\mathrm{Pr}\left(\left(P_1^{\left(k\right)},P_2^{\left(k\right)}\right)=\left(P_1^{*},P_2^{*}\right)\right)=1,$

其中$\left(P_1^{\left(k\right)},P_2^{\left(k\right)}\right)$ 是在第$k$ 次迭代中获得的路径对。

4.2. 预测错误下的鲁棒性分析

预测机制的鲁棒性对于算法的实际效用至关重要。我们的设计采用多层保护机制，以确保即使在预测不准确时，算法依然可靠。首先，通过膨胀因子$\alpha$ 对初始预测值进行保守调整，避免因低估实际距离而导致过早剪枝。其次，算法持续监控搜索状态，并在怀疑预测值不足时自动触发UPDATE-PREDICTION 过程，通过因子$\beta$ 逐步放宽预测边界。这种渐进调整策略能够在处理预测误差的同时，避免搜索空间的急剧扩张。更重要的是，即使在极端情况下，算法最终将回退到不使用预测的标准搜索过程，从而保证了解的存在性和最优性。这种分层鲁棒性设计使得算法能够适应不同质量的预测信息，在预测准确时实现最大加速，在预测较差时保持基线性能。

4.3. 计算效率与对比指标的理论分析

为全面评估所提算法的性能，我们引入以下三项理论对比指标，并给出其形式化定义与计算方式：

1. 总运行时间：设$T_{\text{init}}$ 为算法初始化阶段(包括第一次Dijkstra搜索与距离数组计算)的时间开销，$T_{\text{pred}}$ 为预测模型的推理时间，$T_{\text{search}}$ 为第二条路径的搜索时间。算法的总运行时间$T_{\text{total}}$ 定义为：

$T_{\text{total}}=T_{\text{init}}+T_{\text{pred}}+T_{\text{search}},$

其中，$T_{\text{search}}$ 依赖于预测质量：当预测准确时，剪枝效果显著，$T_{\text{search}}$ 可大幅降低；预测失效时，$T_{\text{search}}$ 退化为经典Suurballe算法的搜索时间$T_{\text{Suurballe}}$ 。

2. 扩展节点数：令$V_{\text{exp}}$ 表示在第二条路径搜索过程中从优先队列$PQ$中弹出并进行松弛操作的节点集合。扩展节点数$N_{\text{exp}}$ 定义为：

$N_{\text{exp}}=\left|V_{\text{exp}}\right|,$

在预测引导的剪枝机制下，$N_{\text{exp}}$ 满足：

$N_{\text{exp}}\le N_{\text{Suurballe}},$

其中$N_{\text{Suurballe}}$ 为经典Suurballe算法在相同实例上的扩展节点数。

3. 加速比：加速比$S$ 用于量化本算法相对于基准方法的性能提升，定义为经典Suurballe算法总运行时间$T_{\text{Suurballe}}$ 与本算法总运行时间$T_{\text{total}}$ 之比：

$S=\frac{T_{\text{Suurballe}}}{T_{\text{total}}}.$

当$S>1$ 时，表明本算法实现了加速；$S=1$ 时，性能与基准持平；$S<1$ 时，性能下降(仅发生于预测严重误导且额外开销显著的情形)。在预测准确时，$T_{\text{search}}\ll T_{\text{Suurballe}}$ ，且$T_{\text{pred}}$ 通常可忽略，此时$S\gg 1$ ，体现出预测机制的有效性。在最坏情况下，算法退化为Suurballe过程，此时$S\approx 1$ ，保证了算法的鲁棒性。这些指标共同构成了评估算法效率与预测引导效果的理论基础，并为后续实验验证提供了明确的量化方向。

5. 结论

本文是将新兴的“带预测的算法”范式首次应用于多路径优化问题，相较于传统的启发式方法，我们创新性地将机器学习预测、双向搜索与经典组合优化算法进行了深度融合与协同。这种多策略协作的框架为解决其他复杂优化问题提供了借鉴模型，展现了不同技术间互补增强的潜力。然而，本研究目前仍存在一定局限性，首先，算法初始化阶段需两次Dijkstra搜索，未来的工作可探索更轻量化的距离估计方法，或针对特定图结构(如层次化网络)设计专用初始化策略。其次所提出的方法尚未通过实际仿真实验验证其性能与鲁棒性，缺乏在不同规模与拓扑结构网络中的实证评估。在未来的研究中，应当引入大规模仿真与真实网络数据实验，理论对比指标(总运行时间、扩展节点数、加速比)为实验评估提供了明确方向。总结而言，本文提出的算法不仅为提升Suurballe算法的计算效率提供了理论思路，也为应对复杂的网络优化挑战提供了新的方法论视角与技术路径。我们相信，这种融合机器学习与经典算法的研究方向，未来将在网络科学、运筹学等领域产生广泛影响。

基金项目

山西省基础研究计划项目(202103021224058)。

NOTES

^*通讯作者。