algorithm - 查找有向图上是否存在从v到t的非简单路径

我正在寻找一个最简单的算法，它可以判断（返回真或假）给定有向图的顶点v和t之间是否存在非简单路径。
我不介意使用bfs、dfs、dijkstra或任何其他有助于解决此问题的算法，我试图获得scc图，但找不到任何好的用途。
任何帮助都将不胜感激！
谢谢您！

最佳答案

Step 0：如果没有从v到t的路径，那么答案是no。
Step 1：在折叠G的所有强连接组件后生成图G'。
：如果顶点“V”是由超过1个顶点组成的某些SCC的一部分，那么肯定存在一个非简单路径。类似地，如果顶点“t”是由多个顶点组成的SCC的一部分，那么答案是肯定的。
Step 2：如果步骤2不正确。然后确定图G’中是否存在从V到T的任何路径，该顶点穿过被折叠成2个或多个顶点的强连通分量的顶点。如果是，那么答案是肯定的，否则答案是否定的。
运行时间：上述算法中每个步骤的O（m+n）。因此总体上Step 3。
编辑：关于如何在线性时间内执行步骤3：
对于G'中的每个顶点，保持两件事：
顶点的大小。（为该SCC顶点收缩的G顶点数）
这个顶点是否可以从t到达（我们可以通过在g'的反向图上从t运行dfs来计算这个值）
现在，如果存在从G’中的顶点’到顶点t的路径，该函数通过SCC（int顶点）将返回true，该顶点T通过大小>＝2的任何SCC顶点。函数的伪代码：

boolean throughSCC(int vertex){
    if(!reachable[vertex]){
        return false;
    }
    if(sz[vertex] >= 2){
        return true;
    }
    for(all neighbours X of vertex){
         if(throughSCC(X)){
              return true;
         }
    }
    return false;
}