algorithm - DAG 中的最长路径

Question

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

Answer 1

您的第二个选项不正确：DFS 不会探索所有可能的路径，除非您的图形是树或森林，并且您从根开始。我知道的第二种算法是对权重求反并找到最短路径，但它比您列为 #1的顶级排序 + DP 算法要慢一些。

Answer 2

使用 "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 paths

Answer 3

不需要 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。