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