peoplePleaser's blog

By peoplePleaser, history, 3 years ago, In English

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 iterating over the vertices in that order and update the distances accordingly. Any suggestions/help would be appreciated or maybe we can prove there doesn't exist a faster method. Thanks!

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it