1、引言

在图中寻找多个顶点对之间的路径是一个基础性问题，应用广泛，包括网络路由、交通系统和网络安全等领域。k-不相交路径（kDP）问题要求在源点和目标点之间找到 k 条路径，并确保这些路径在顶点或边上互不重叠，以提高网络的容错性和负载均衡能力。

ShareDP 方法概览

• 合并拆分图：将多个单独的拆分图合并为一个统一结构

• 共享遍历：在多个查询间合并遍历操作，提高效率

虽然已有大量研究关注单个顶点对的 k-不相交路径问题，但现代应用通常需要同时处理多个类似查询。本文提出了一种新的算法 ShareDP，能够通过在多个查询间共享计算，显著提升查询效率，相较于现有方法具备明显的性能优势。

2、k-不相交路径问题

k-不相交路径（kDP）问题的核心目标是：在给定图 G=(V,E)G = (V, E)G=(V,E) 及顶点对 (s,t)(s, t)(s,t) 的情况下，找到 k 条彼此 顶点不相交（vertex-disjoint）或 边不相交（edge-disjoint）的路径。本文重点研究顶点不相交路径，因为它是更严格的约束形式。

例如，在下图所示的图中，顶点对 (a,h)(a, h)(a,h) 存在两条不相交路径：

p1: a→b→c→d→h（红色）

p2: a→e→f→g→h（蓝色）

批量 kDP 问题（Batch-kDP） 是 kDP 问题的扩展版本，要求同时为多个顶点对寻找 k 条不相交路径。例如，在网络路由中，需要同时处理多个路由请求，因此高效的批量 kDP 求解方法至关重要。

3、现有方法的局限性

目前主流的 kDP 求解方法主要包括：

基于流的算法：

原始图转换为流网络，并使用最大流算法（如 Ford-Fulkerson 算法）求解 kDP，时间复杂度为 O(k∣E∣)O(k|E|)O(k∣E∣)。

但当需要处理多个查询时，每个查询都需要独立进行图转换，缺乏计算共享。

基于不相交约束的方法：

逐个寻找路径，并确保后续路径不与已找到的路径相交。

由于涉及路径组合搜索，最坏情况下复杂度达到 O(∣V∣!)O(|V|!)O(∣V∣!)，在大规模图或较大 k 值下难以实际应用。

单源方法：

适用于从单个源点到多个目标点的查询，但难以推广到一般的 kDP 问题，且无法高效处理批量查询。

批量 kDP 问题的特殊性在于：每个查询涉及不同的 kDP 任务，传统批量处理方法难以有效应用，因此需要新的优化策略。

4、ShareDP 算法

ShareDP 的核心创新在于 在多个 kDP 查询之间共享计算和存储，主要分为两个阶段：

合并拆分图表示（Merged Split-Graph Representation）

传统流式算法通过拆分图来保证路径不相交，ShareDP 通过 隐式合并 各查询的拆分图，避免冗余计算。

这种方法显著减少了内存占用和计算开销。

共享遍历的优化路径查找（Optimized Path-Finding with Shared Traversal）

采用 共享遍历 机制，使多个查询可以在相同的遍历过程中进行路径搜索，从而减少重复计算。

采用双向 BFS（从源点和目标点同时搜索），进一步提升搜索效率。

5、实验结果

ShareDP 在 12 个真实数据集上与 5 种基线方法（BatchEnum、Penalty、SCB+、IST 和 maxflow）进行了对比，实验结果表明 ShareDP 具有显著的性能优势：

整体性能优势

ShareDP 在所有数据集上都具有最低的运行时间，处理效率优于所有基线方法。

对大 k 值的适应性

随着 k 的增加，ShareDP 相较于 maxflow 方法的性能优势更加明显，展现了良好的可扩展性。

批量查询的计算共享性

处理的查询数量越多，ShareDP 的单位查询时间越低，表明计算共享机制有效减少了重复计算。

复杂图上的优势

在较大规模或路径稀疏的图上，ShareDP 的优化效果尤为突出。

消融实验

进一步分析表明，合并拆分图 和 共享遍历 是提升 ShareDP 性能的关键，尤其是合并拆分图带来的计算节约最为明显。

6、影响与应用

ShareDP 的高效计算能力在多个领域有重要应用价值：

网络路由：加速通信网络中的路径规划，提高网络响应能力和容错性。

交通系统：用于替代路线规划，提高道路网络的稳定性和通行能力。

网络安全：帮助分析不相交的通信路径，提升威胁检测和入侵防御能力。

图分析：可作为复杂图分析任务的基础模块，提升多对连通性计算的效率。

特别是在高吞吐量场景下（如大规模网络查询、实时路由优化等），ShareDP 的计算共享特性可以大幅降低计算成本，提高系统响应速度。

7、结论

ShareDP 在批量 k-不相交路径问题上实现了突破性的优化：

合并拆分图表示：消除冗余图转换，减少存储和计算开销。

共享遍历机制：提高查询间计算共享程度，避免重复操作。

实验验证：在多个数据集上表现优越，性能随查询数和 k 值增加而更具优势。

这种共享计算思想不仅适用于 kDP 问题，还可能启发其他图算法的优化，推动更广泛的图计算研究与应用。