计算简单有向图的两个给定顶点之间的所有边不相交路径
Compute all edge-disjoint paths between two given vertices of a simple directed graph
许多类似的问题已经被问到，但没有解决我的情况：给定一个简单的有向未加权图中的两个顶点和一个整数 k，我如何找到所有 k -顶点之间的边不相交路径的元组？ （特别是，我对 k 是起始顶点的出度的情况感兴趣。）
我知道 Suurballe 的算法会给我 k 个边缘不相交的路径，但它会（不确定地）选择一个解决方案，而不是给我所有的解决方案。
似乎像 Edmonds-Karp 这样的最大流算法是相关的，但它们不计算路径。
JGraphT 中是否已经有任何算法可以满足我的要求？
这是一个简单的递归方法：
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 的所有没有流量的弧。
许多类似的问题已经被问到，但没有解决我的情况：给定一个简单的有向未加权图中的两个顶点和一个整数 k，我如何找到所有 k -顶点之间的边不相交路径的元组？ （特别是，我对 k 是起始顶点的出度的情况感兴趣。）
我知道 Suurballe 的算法会给我 k 个边缘不相交的路径，但它会（不确定地）选择一个解决方案，而不是给我所有的解决方案。
似乎像 Edmonds-Karp 这样的最大流算法是相关的，但它们不计算路径。
JGraphT 中是否已经有任何算法可以满足我的要求？
这是一个简单的递归方法：
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 的所有没有流量的弧。