kunzmilan wrote: > On Jun 20, 10:40 am, mirchi <[EMAIL PROTECTED]> wrote: > > can anyone please tell me how to find > > single source longest path in a directed acyclic graph?? > Write its adjacency matrix A(ij) = 1, if arc i to j exists, 0 > otherwise. > Find the consecutive powers A^k. > When a new nonzero element appears in A^k, then there exists the path > ij of length k in this graph. > kunzmilan
Once again, the graph in question is acyclic. This means that there is a unique path from the starting vertex to each vertex reachable from it. Simply finding the distance of all reachable vertices reveals the furthest vertex and therfore the longest path. This can be done just by a simple depth first traversal starting from the source vertex. I don't think we need to look to doing large matrix multiplications/ exponentiation for something this simple, especially if the number of nodes is large. Muntasir --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
