已经提出了许多类似的问题，但没有完全解决我的情况:给定一个简单的有向未加权图中的两个顶点和一个整数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 的无流量的弧都可以安全地丢弃。
关于algorithm - 计算简单有向图的两个给定顶点之间的所有边不相交路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63171451/