Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Question Detail: 

Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$.
I have an algorithm in which I will run a DFS(Depth First Search) but if DFS finds $t$ then it will not change the color(from white to grey) of any of the nodes which comes in the path $s \rightsquigarrow t$ so that if this is the subpath of any other path then also DFS goes through this subpath again.For example consider the adjacency list where we need to find the number of paths from $p$ to $v$.
$$\begin{array}{|c|c c c|} \hline p &o &s &z \\ \hline o &r &s &v\\ \hline s &r \\ \hline r &y \\ \hline y &v \\ \hline v &w \\ \hline z & \\ \hline w &z \\ \hline \end{array}$$ Here DFS will start with $p$ and then lets say it goes to $p \rightsquigarrow z$ since it doesnot encounter $v$ DFS will run normally.Now second path is $psryv$ since it encounter $v$ we will not change the color of vertices $s,r,y,v$ to grey.Then the path $pov$ since color of $v$ is still white.Then the path $posryv$ since color of $s$ is white and similarly of path $poryv$.Also a counter is maintained which get incremented when $v$ is encountered.

Is my algorithm correct? if not, what modifications are needed to make it correct or any other approaches will be greatly appreciated.

Note:Here I have considered the DFS algorithm which is given in the book "Introduction to algorithms by Cormen" in which it colors the nodes according to its status.So if the node is unvisited , unexplored and explored then the color will be white,grey and black respectively.All other things are standard.

Asked By : Saurabh

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3078

Answered By : Nicholas Mancuso

Your current implementation will compute the correct number of paths in a DAG. However, by not marking paths it will take exponential time. For example, in the illustration below, each stage of the DAG increases the total number of paths by a multiple of 3. This exponential growth can be handled with dynamic programming.

Computing the number of $s$-$t$ paths in a DAG is given by the recurrence, $$\text{Paths}(u) = \begin{cases} 1 & \text{if } u = t \\ \sum_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\ \end{cases}$$

A simple modification of DFS will compute this given as

def dfs(u, t):     if u == t:         return 1     else:         if not u.npaths:             # assume sum returns 0 if u has no children             u.npaths = sum(dfs(c, t) for c in u.children)         return u.npaths 

It is not difficult to see that each edge is looked at only once, hence a runtime of $O(V + E)$.