@Amol I think the solution given above is fine except that i missed to initialize A[src] =1. Thats the reason why u end up getting 0's for all A[i]'s.
Modification to the third step: 3) Scan the linearized list from left to right initialize all the corresponding values in array A to 0. Set A[src]=1. On Wednesday, 30 May 2012 23:49:46 UTC+5:30, Amol Sharma wrote: > > just check, In the above loop(posted by lucifer) it will only return zero > everytime.. > > corrected after getting the linearized list after topological sort : > > take an auxillary array, A of size N....*A[i] represent the number of > paths from i to target. > * > initialize A[target] to 1 and values at all other indexes as zero . > > > Do this in the While loop -- > scan the linearized list from target and move towards source.... > as soon as you see a node x in the list while scanning then A[x]=sum of > all A[j] where j are all the childs of x. > > > when you reach source return A[source] > > > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> > > > > > > > > On Wed, May 30, 2012 at 11:11 PM, sourabh datta <[email protected]>wrote: > >> Y? >> On May 30, 2012 9:58 PM, "Amol Sharma" <[email protected]> wrote: >> >>> @lucifer: your algo seems correct but in the last step you should start >>> loop from target to source rather from source to target.. >>> -- >>> >>> >>> Amol Sharma >>> Third Year Student >>> Computer Science and Engineering >>> MNNIT Allahabad >>> <http://gplus.to/amolsharma99> >>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> >>> >>> >>> >>> >>> >>> >>> >>> On Mon, May 28, 2012 at 1:08 AM, Lucifer <[email protected]> wrote: >>> >>>> 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 <[email protected]> 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 <[email protected]> >>>> 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 [email protected]. >>>> > > To unsubscribe from this group, send email to >>>> > > [email protected]. >>>> > > 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > On Wednesday, 30 May 2012 23:49:46 UTC+5:30, Amol Sharma wrote: > > just check, In the above loop(posted by lucifer) it will only return zero > everytime.. > > corrected after getting the linearized list after topological sort : > > take an auxillary array, A of size N....*A[i] represent the number of > paths from i to target. > * > initialize A[target] to 1 and values at all other indexes as zero . > > > Do this in the While loop -- > scan the linearized list from target and move towards source.... > as soon as you see a node x in the list while scanning then A[x]=sum of > all A[j] where j are all the childs of x. > > > when you reach source return A[source] > > > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> > > > > > > > > On Wed, May 30, 2012 at 11:11 PM, sourabh datta <[email protected]>wrote: > >> Y? >> On May 30, 2012 9:58 PM, "Amol Sharma" <[email protected]> wrote: >> >>> @lucifer: your algo seems correct but in the last step you should start >>> loop from target to source rather from source to target.. >>> -- >>> >>> >>> Amol Sharma >>> Third Year Student >>> Computer Science and Engineering >>> MNNIT Allahabad >>> <http://gplus.to/amolsharma99> >>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/> >>> >>> >>> >>> >>> >>> >>> >>> On Mon, May 28, 2012 at 1:08 AM, Lucifer <[email protected]> wrote: >>> >>>> 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 <[email protected]> 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 <[email protected]> >>>> 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 [email protected]. >>>> > > To unsubscribe from this group, send email to >>>> > > [email protected]. >>>> > > 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/b70SZxzUv3YJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
