Longest Path in a weighted DAG
Разница между en2 и en3, 41 символ(ов) изменены
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! 

История

 
 
 
 
Правки
 
 
  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)