DAG 中的最长路径 [英] Longest path in a DAG

问题描述

要找到 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.

这篇关于DAG 中的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！