On Jun 24, 10:05 am, pramod <[EMAIL PROTECTED]> wrote:
> For DAGs I don't think there's a unique path from a start vertex to
> each vertex reachable from it. There could be many paths.
>
> One way to solve this problem is to topologically sort the DAG and
> start from the end and move backwards till the start vertex and keep
> track of the longest path.
> The last vertex has no paths from it to anywhere so the longest path
> is of zero length.
> The vertex before this will have longest path of 1 if it has an edge
> to the last vertex.
> So in general, when we encounter a vertex u then we check each edge
> from it (u, v) and if vertex v has a longest path of length l then the
> vertex u has a path of length l+1. We just need to find the longest of
> these.
> When we come to the start vertex, we get the required answer. The
> while thing is linear time work.
>
> Let me know if this is wrong.
Well, we need to do this for each "last vertex". There could be many
nodes such that they dont lead to other nodes.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
