DAG中的最长路径
DAG中的最长路径
提问于 2012-05-23 09:50:52
为了找到DAG中的最长路径，我知道有两种算法: algo 1:进行拓扑排序+对排序结果使用动态编程~或algo 2:使用DFS枚举DAG中的所有路径，并记录最长的路径。似乎使用DFS枚举所有路径比使用algo 1更复杂，是真的吗？
回答 3
Stack Overflow用户
发布于 2012-05-23 10:14:04
您的第二个选择是错误的: DFS不会探索所有可能的路径，除非您的图是树或森林，并且您从根开始。我知道的第二种算法是求负权重并找到最短路径，但它比你列为#1的top sort + DP algorithm要慢一些。
Stack Overflow用户
发布于 2012-05-23 11:39:49
使用“DFS”枚举DAG中的所有路径：
import numpy as np
def enumerate_dag(g):
def enumerate_r(n, paths, visited, a_path = []):
a_path += [n]
visited[n] = 1
if not g[n]:
paths += [list(a_path)]
else:
for nn in g[n]:
enumerate_r(nn, paths, visited, list(a_path))
paths, N = [], len(g)
visited = np.zeros((N), dtype='int32')
for root in range(N):
if visited[root]: continue
enumerate_r(root, paths, visited, [])
return pathsStack Overflow用户
发布于 2012-05-24 20:29:22
不需要DFS。算法:取一个DAG G。每条弧包含一个变量E
for each node with no predecessor :
for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
for each of his leaving arcs, E=max(E(entering arcs))+1.当所有节点都已被处理时，max_path是边中最高的E。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/10712495
复制相关文章
相似问题
腾讯云开发者
