要找到一个DAG最长的路径，我所知道的2算法：算法中1：做一个拓扑排序+使用动态编程的排序结果〜或〜算法中2：枚举DAG所有路径使用DFS，并记录最长。这似乎是列举所有路径与DFS具有更好的复杂性比算法中1。是真的吗？

To find the longest path in a DAG, I'm aware of 2 algorithms: algo 1: do a topological sort + use dynamic programming on the result of the sort ~ or ~ algo 2: enumerate all the paths in the DAG using DFS, and record the longest. It seems like enumerating all the paths with DFS has better complexity than algo 1. Is that true?

推荐答案

您的第二个选项是不正确的：DFS不寻求一切可能的路径，除非你的图是一棵树或一片森林，你从根部开始。第二算法，我知道是否定的权重，并找到最短路径，但它比顶部排序+ DP的算法你列为＃1。

Your second option is incorrect: DFS does not explore all possible paths, unless your graph is a tree or a forest, and you start from the roots. The second algorithm that I know is negating the weights and finding the shortest path, but it is somewhat slower than the top sort + DP algorithm that you listed as #1.