1

A problem to find Number of paths between two particular vertices of a directed graph and if there exists a cycle in between them then the number of paths are infinite, so I know the algorithm to find cycle in the whole graph but not any two particular vertices, so it will be helpful for me if anyone explain it.

prashu Gupta
  • 15
  • 8

1 Answers1

1

So, we can divide this problem into two sub parts.
If there is a cycle between U (source) and V (destination) then the answer will be infinite. So in one DFS we will start from U until we get V. Similarly starting from V until we get U. If we get reach both from both the ways then the desired answer is infinite.

Now the main part. Run a normal DFS from source U and start visiting every node as true, if you encounter the destination node that is V don't mark it as true and then simply continue from there. (Cycles in between this process can easily be detected).

akhem301
  • 79
  • 1
  • 1
  • 9
  • n is a number of vertices and k is a number of edges n=5 k=5 {1 2, 4 2, 2 3, 3 4, 4 5} and U=1 and V=5 there is no path from 5 to 1 then also it form cycle in between 1 and 5 – prashu Gupta Nov 20 '17 at 04:50