pramod 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.
Yes, for a DAG there certainly can be multiple paths to the same node. I'm afraid I kept forgetting that a DAG is not the same as a tree. Thank you for pointing that out, and I'm sorry if I misled anyone. > 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. I think your approach is correct. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
