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

Question

已经提出了许多类似的问题，但没有完全解决我的情况：给定一个简单的有向无权图中的两个顶点和一个整数k，我怎样才能找到顶点之间边缘不相交路径的所有 k 元组？（特别是，我对k是起始顶点的出度的情况感兴趣。）

我知道 Suurballe 的算法会给我 k 个边缘不相交的路径，但它会（非确定性地）解决一个解决方案，而不是给我所有的解决方案。

似乎像 Edmonds-Karp 这样的最大流量算法是相关的，但它们不计算路径。

JGraphT 中是否已经有任何算法可以满足我的要求？

标签： algorithmgraphdirected-graphjgrapht

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 的所有没有流动的弧都可以安全地丢弃。