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

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.