algorithm - 查找边缘不相交的路径(不是数字，路径)

Question

给定一个有向图，我们可以使用 edmonds-karp 或 ford-fulkerson 算法来找到有向图中边不相交路径的最大数量。

假设 G 中有 k 条边不相交的路径，如何在多项式时间内找到实际路径？我最好的选择是 BFS，一旦找到路径，就将这些边标记为已使用。

非常感谢!

Answer 1

您可以使用流分解。它是这样的:

1. 让我们从起始节点运行深度优先搜索并忽略具有零流或负流的边。

2. 一旦到达终端节点，从起始节点到终端节点的路径上的所有边的流量减去一个并打印它们(它们形成一条路径)。

3. 只要终端节点可达，就继续这样做。

每次运行都使用多项式时间，并从图中找到并删除一条路径。不相交路径的数量显然是多项式的，因此该算法具有多项式时间复杂度。

您也可以使用广度优先搜索(您仍然需要忽略具有非正流的边缘)。