Longest Path in a weighted DAG
Difference between en2 and en3, changed 41 character(s)
Does there exist a way an efficient method to find the longest path in a DAG among all possible paths? I know how to solve this in $O(V*(V+E))$ by considering each vertex as the source, and then using topo sort, and iterateing over the vertices in that order and update the distance followed by simple relaxation of edgess accordingly. Any suggestions/help would be appreciated or maybe we can prove there doesn't exist a faster method. Thanks! 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English peoplePleaser 2021-01-10 20:55:14 41
en2 English peoplePleaser 2021-01-10 20:54:29 81 (published)
en1 English peoplePleaser 2021-01-10 20:52:09 387 Initial revision (saved to drafts)