Fra*_*ank 11 algorithm graph directed-acyclic-graphs
为了找到DAG中最长的路径,我知道2种算法:算法1:进行拓扑排序+对排序结果使用动态编程〜或〜算法2:使用DFS枚举DAG中的所有路径,并记录最长的.似乎枚举DFS的所有路径都比算法更复杂1.这是真的吗？
das*_*ght 8
您的第二个选项不正确:DFS不会探索所有可能的路径,除非您的图形是树或森林,并且您从根开始.我知道的第二种算法是否定权重并找到最短路径,但它比你列为#1 的顶级排序+ DP算法慢一些.
归档时间：
14 年，1 月 前
查看次数：
20529 次
最近记录：
11 年 前