Longest Path in a weighted DAG

Правка en1, от peoplePleaser, 2021-01-10 20:52:09

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^2)$$$ by considering each vertex as the source, and then using topo sort, 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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский peoplePleaser 2021-01-10 20:55:14 41
en2 Английский peoplePleaser 2021-01-10 20:54:29 81 (published)
en1 Английский peoplePleaser 2021-01-10 20:52:09 387 Initial revision (saved to drafts)