algorithm - 计算简单有向图的两个给定顶点之间的所有边不相交路径

Question

已经提出了许多类似的问题，但 non 正好解决了我的情况:给定一个简单的有向未加权图中的两个顶点和一个整数 k，我怎样才能找到顶点之间边不相交路径的所有 k 元组？ (特别是，我对 k 是起始顶点的出度的情况感兴趣。)
我知道 Suurballe 的算法会给我 k 条边不相交的路径，但它会(非确定性地)确定一个解决方案，而不是给我所有的解决方案。
似乎像 Edmonds-Karp 这样的最大流算法是相关的，但它们不计算路径。
JGraphT 中是否有任何算法可以满足我的要求？

Answer 1

这是一个简单的递归方法:

if k is 0, output [] and return
otherwise, choose an arbitrary arc from the source vertex
for all paths p that start with that arc and end at the sink,
    for all k-1 tuples T in the graph where the arcs in p are removed,
        output [p] + T

这种方法可以通过修剪递归树的部分来改进。最简单的想法是移除到源顶点的所有弧，因为如果一条路径使用来自源顶点的两条弧，我们将不会在断开源和汇之前到达 k。
该想法的更广泛版本使用最大流量来识别可以作为解决方案一部分的弧。计算从源到汇的最大流量。根据流分解定理，当且仅当流的值至少为 k 时，存在至少一个边不相交路径的 k 元组。如果这些条件都成立，那么就有一个解，使用了载流的弧集，所以这个集需要保留。为了测试其他的，计算残差图的强连通分量(没有流动的弧出现向前，有流动的弧出现向后)。从一个 SCC 到另一个 SCC 的所有没有流动的弧都可以安全地丢弃。