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