Find if there is a non-simple path from v to t on a directed graph

Question

I'm on a search for the most simple algorithm that could tell (returns true or false) if there is a NON-SIMPLE path between vertex v and t given a directed graph.

I don't mind using BFS, DFS, Dijkstra or any other algorithm that could help solving this problem, I was trying to get the SCC graph, but I couldn't find any good use to it.

Any help would be appreciated!

Thank you!

Answer 1

Step 0: If there is no path from v to t, then answer is NO.

Step 1: Make the graph G' after collapsing all the strongly connected components of G.

Step 2: If the vertex 'v' is a part of some SCC consisting of more than 1 vertex, then there definitely exists a non-simple path. Similarly if vertex 't' is a part of some SCC consisting of more than 1 vertex then answer is YES.

Step 3: If step2 is not true. Then determine if there exists any path from v to t in graph G' that goes through a vertex that was collapsed into a strongly connected component of 2 or more vertices. If so, then answer is YES else the answer is NO.

Running Time: O(M+N) for each of the steps in the above algorithm. Thus overall O(M+N).

Edit: On how to do step 3 in linear time:

For every vertex in G', maintain two things:

1. Size of that vertex. (No. of vertices of G that were contracted for this SCC vertex)
2. Is this vertex reachable from t or not. (We can compute this by running dfs from t on the reverse graph of G')

Now the following function throughSCC(int vertex) will return true if there exists a path from the vertex 'vertex' in G' to the vertex t that goes through any SCC vertex of size >= 2. Pseudocode for the function:

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;
}

Answer 2

Since the SCC algorithms are slightly annoying, here's an alternative algorithm. Traverse once to determine which vertices are reachable from v. Traverse backward from t, ignoring vertices unreachable from v, looking for a cycle. Report the existence of a non-simple path iff such a cycle is found.