有没有从s-t经过特殊节点的路径？

Question

我在这个网站上看到过这个问题的一些变体，但不完全是这个。

问题

我有一个未加权的图 G=(V,E)，最好我需要制定一个适用于有向图和无向图的解决方案。

V的一个子集是W，这些是特殊的节点。 我需要找出是否有可能找到一条从起始节点 s 到结束节点 t 的路径，该路径经过 W 中的一个或多个特殊节点。这是一个节点不重复的简单路径，并且它在多项式时间内必须 运行

所以我只需要输出'true'或'false'。

我目前的尝试

首先，我认为对于每个特殊节点 i W，我会 运行 一个可以找到节点 w 的 bfs，然后 运行 从节点 w 到 t 的新 bfs。 大致是这样的：

for w in W:
    firstpath = bfs from s to w
    secondPath = bfs from w to t (that does not touch nodes in firstpath)
    if firstpath + second == path from s to t:
         return True
    else:
        continue

但在这里，问题可能是“firstpath”可能会阻塞从 w 到 t 的可能路径。

任何可以保证没有“节点冲突”的问题的多项式算法的想法

Answer 1

对于无向图，我们可以尝试 W 中的所有 w，使用最大流寻找从 w 到 s 和 t 的两条 node-disjoint 路径。不幸的是，我不确定这是否可以推广到有向图。