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
-~----------~----~----~----~------~----~------~--~---
