On 11/30/07, John <[EMAIL PROTECTED]> wrote:
>
> Given a DAG and two vertices s and t , give a linear time number of
> paths between s and t in G.
> How does topological sort help in finding the same ?
Hi Joh,
you can do a dynamic programming algorithm Your state is S[x] = number
of path going from s to x, s is the initial vertex. It's easy to see
that equation holds :
S[x] = sum { S[v], for all v neighbor of x }
Think about base cases and make a memorized function to get the answer.
Hope this help,
Caio
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
