algorithm - 有向图中的 K 边不相交路径

Question

给定G = (V,E)中的两个顶点u和v和一个正整数k，描述一个算法来判断是否存在从u到v的k条边不相交的路径。如果判断问题的答案是肯定的，描述如何计算一组 k 边不相交的路径。

解决方案: 运行从 u 到 v 的最大流(给图 G 中的所有边赋予 1 的权重，以便一条边只能是从 u 到 v 的一条路径的一部分)并得到流量的值(value)。如果流量的值为 k，那么我们对决策问题的答案是肯定的。

现在为了找到所有这样的路径，通过从 u 执行 BFS 找到最小切割，因此我将进行顶点划分，它将顶点分成 2 组，在最小切割的每一侧。

然后我是否需要再次执行从 u 到 v 的 DFS 以查找所有只有这些顶点的路径，这些顶点位于我从最小切割得到的两个分区集中。

或者还有其他更清洁的方法吗？得到所有的 k 边不相交路径。

Answer 1

一旦有了流程，您就可以按照流程提取边缘不相交的路径。

起始节点将有 k 条流沿着 k 条边离开 u。

对于这些边中的每一个，您都可以继续沿流出流的方向移动以提取路径，直到到达 v。您需要做的就是标记您已经使用过的边以避免重复边。

对离开 u 的 k 个流量单元中的每一个重复以提取所有 k 个路径。

伪代码

repeat k times:
  set x to start node
  set path to []
  while x is not equal to end node:
      find a edge from x which has flow>0, let y be the vertex at the far end
      decrease flow from x->y by 1 unit
      append y to path
      set x equal to y
  print path