Since it s a DAG, just multiply all the edge weights by -1. Then use dijkstra's to find the min shortest path.
Wether some of the edge weights are negative or not, it shouldn't effect the solution as when using dijkstra's, we take the min node potentials. ,--- This can be proven.... On Aug 20, 10:05 am, Vineeth Kashyap <[EMAIL PROTECTED]> wrote: > 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.- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
