问题:
设G =(V,E)是n> = 3个具有m个边的顶点的有向图.顶点集V包括三个特殊顶点a,v和b.如果存在,则通过v找到从a到b的简单路径.(简单路径是没有重复顶点的路径.)
我相信这个问题应该/可以通过Max Flow算法解决,但我不知道如何.它让我想起了Max Flow算法,它有多个源,边缘有容量1.任何人都知道如何将问题简化为最大流量算法？
如果我将顶点b设置为接收器,我无法确定它是否包含v.如果我将v设置为接收器,当达到v时如何继续？
以下应该有效：
找到从到 的所有不包含顶点的最小路径。您可以通过（例如）在没有 vertex 的图上进行 DFS 来获得这些。如果没有其他路径仅包含来自 的顶点，我们就说该路径是最小的。avbba-vpa-vp'p
对于每个最小a-v路径，尝试找到一条从v到b忽略已经属于该a-v路径的顶点的路径。如果你找到这样的东西，你就完了。
备注：请注意，路径的数量可能会呈指数增长，但正如我在评论中指出的那样，至少这个问题的广义版本似乎可以简化为 TSP，因此可能非常困难。