1) Linearize the DAG using DFS. ( topological sorting)
2) Now take an array of size A[N] ( N - nodes in the DAG ), where A[i]
mimics the 'i'th node in the linearized list.
3) Scan the linearized list from left to right to get to the source
node and initialize all the corresponding values in array A to 0.
i.e. A[1] to A[src].
4) Now use the below equation to calculate the value for no. of paths
to any node after the src node in the linearized list as follows.
i= src + 1;
while( i <=dest )
{
A[i]= sum of all ( A[j] 's);
// where (j < i) and there is a directed edge from j to
i ....
++i;
}
5) Return A[dest].
On May 24, 11:23 pm, MeHdi KaZemI <mehdi.kaze...@gmail.com> wrote:
> Hi.
>
> DFS( k ) returns the number of paths from node k to your destination.
> so DFS( k ) is equal to the sum of DFS( p ) such that there is a forward
> edge from k->p.
>
> You have to memoize DFS for each node to prevent "calculating the number of
> paths from that node" more than one time. I do that with array 'ans'.
> Read the code and take a look at the picture and ask your question if there
> is any.
>
>
>
>
>
>
>
>
>
> On Thu, May 24, 2012 at 4:50 PM, Ashish Goel <ashg...@gmail.com> wrote:
> > My bad, i am not able to conceptualize this known problem, can anyone help
>
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> MeHdi KaZemI
>
> paths in dag.cpp
> < 1KViewDownload
>
> paths in dag.png
> 22KViewDownload
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
