Hi Nima, I think what you are doing is finding the NUMBER OF PATHS rather then THOSE PATHS as sequence of nodes. Counting number of paths between two given nodes is pretty straight forward using DFS (Refer CLRS) You might be using this information to yield the paths as sequence of nodes but could you be more elaborate.
_dufus On Aug 28, 2:37 pm, Nima Aghdaii <[email protected]> wrote: > assume that you want to write this function: f(source, dest) > we can reduce it to f(source) because destination will not change. > now, for every 'u' which is a neighbor of 'source', if we have already > calculated f(u) before, we can calculate f(source) : > f(source) = Sigma [ f(u) ] > > you can calculate it simply with a DFS. > like this: > > int memo[num_of_vertices]; > memset(memo, -1, sizeof memo); > memo[dest]=1; > > int f(int src) > { > if(src==dest || memo[src]!=-1) > return memo[src]; > res=0; > for(int i=0; i<adj[src].size(); i++) > res += f ( adj[src][i] ) ; > memo[src]=res; > return memo[src]; > > } > > I just used memo to memorize the calculated nodes. > If you wanna use dynamic programming without memoizing, I think you should > apply a Topological Sort, but this one is briefer. > > for your example: > C > A-->B / \D--->E > \ F/ > > f(A)=f(B) > f(B)=f(C)+f(F) > f(C)=f(F)=f(D) > f(D)=f(E)=1 //destination > so: > f(C)=f(F)=1 > f(B)=1+1 =2 > f(A)=2 > > Hope its clear enough. :) > > Bests, > Nima > > On Thu, Aug 27, 2009 at 10:02 AM, ankur aggarwal > <[email protected]>wrote: > > > > > @nima > > could not understand your soln.. > > > try wid an example.. > > > On Thu, Aug 27, 2009 at 1:40 PM, Nima Aghdaii <[email protected]>wrote: > > >> you can use dynamic programming. > >> we wanna solve: f(n1, n2) > >> f(n1, n2) : > >> res=0 > >> for each u such that we have n1->u > >> res += f(u, n2) // which is calculated before > > >> (actually you need a one dimensional array for the source) > >> O(V+E) > > >> Good luck, > >> Nima > > >> On Wed, Aug 26, 2009 at 1:33 AM, ankur aggarwal <[email protected] > >> > wrote: > > >>> given a directed graph and node n1 and n2 > >>> find all possible path between them > > >>> i think graph is acyclic .. > >>> otherwise there are infinte path we can write > > >>> eg > > >>> for node "a" and "d" are there > >>> we have a cycle node "b" to "c" and "c" to "b" > > >>> a-> b->c->b->d > >>> a-> b->c->b->c->b->d > >>> etc > > >> -- > >> Nima Aghdaii > > >> "The ideal situation occurs when the things that we regard as beautiful > >> are also regarded by other people as useful." > >> -Donald Knuth- > > -- > Nima Aghdaii > > "The ideal situation occurs when the things that we regard as beautiful are > also regarded by other people as useful." > -Donald Knuth- --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
