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

Question

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

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

非常感谢！

Answer 1

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

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

2. 到达终端节点后，从通过从起始节点到终端节点的路径上的所有边的流中减去 1 并打印它们（它们形成路径）。

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

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

您也可以使用广度优先搜索（您仍然需要忽略非正流的边）。