Longest Path in a weighted DAG
Difference between en1 and en2, changed 81 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(n^2V*(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 edges. 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)