algorithm - 最大流量 - 通过顶点 - 如何？

Question

问题:

设 G = (V, E) 是 n >= 3 个顶点和 m 条边的有向图。顶点集V包括三个特殊顶点 a、v 和 b。找到一条从 a 到 b 通过 v 的简单路径(如果存在)。 (简单路径是没有重复顶点的路径。)

我相信这个问题应该/可以用最大流算法来解决，但我不确定如何解决。这让我想起了具有多个源的最大流算法，其中边的容量为 1。有人知道如何将问题简化为最大流算法吗？

如果我将顶点 b 设置为下沉，我不能确定它是否会包含 v。如果我将 v 设置为下沉，当达到 v 时我该如何继续？

Answer 1

以下应该有效:

• 找到从a到v的所有最小路径，不包含顶点b。您可以通过(例如)图上没有顶点 b 的 DFS 来获得这些。我们说 a-v-path p 是最小的，如果没有其他 a-v-path p' 只包含顶点来自p。

• 对于每个最小的 a-v 路径，尝试找到从 v 到 b 的路径，忽略已经属于 的顶点code>a-v-路径。如果你找到这样的东西，你就完了。

备注:请注意，路径的数量可能呈指数增长，但正如我在评论中指出的那样，至少这个问题的一般化版本似乎可以简化为 TSP，因此可能很难。