在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不寻求一切可能的路径，除非你的图是一棵树或一片森林，你从根部开始。第二算法，我知道是否定的权重，并找到最短路径，但它比<略慢href="https://en.wikipedia.org/w/index.php?title=Longest_path_problem&oldid=525448430#Algorithms_for_acyclic_graphs"相对=nofollow>顶部排序+ 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屋！