>No, longest path isn't that easy. We can find the Halminton path as well as >the longest path, but...
That's right. I misread the question. I thought the shortest path was being asked for. But, since the graph is a DAG, this is actually an easier problem. There is a unique path from the source to every other node reachable from it. Thus we can easily find the distance of all reachable nodes from the source vertex using a simple DFS or BFS. After that it is simply a matter of finding the maximum of these values. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
