I have an strongly connected graph and I want to find the pairs of nodes with minimum 2 paths between them. Can you give me an idea of algorithm or something which I can use? Thanks.
First thing that comes to mind, is to utilize DFS in the following manner:
DFS starts on some vertex v1, and "discovers" vertices one by one. Every discovered vertex recursively starts its own DFS and gets "processed" after its recursion returns.
Let's assume that there are two directed paths from v1 to v2. In that case, v2 is going to be "discovered" (by means of one of those two paths going from v1 to v2) and eventually "processed". However, v1's recursion is not over yet. The DFS flow is going to reach v2 for the second time (this time by using the second path from v1 to v2), but this time, v2 is in "processed" state already.
So whenever we encounter a "processed" vertex, it implies there is a second path going to it.
This method works for all sorts of directed graphs, it does not take advantage of the fact that the graph is strongly connected, so possibly this fact could be used for more optimal solution.
Also note that for undirected graphs the situation is much more relaxed - we simply need to detect all cycles in the graph, and every pair of vertices in the cycle would have two paths between them. In directed graph, cycle is one-way so we cannot assume double path between members of a cycle.