algorithm - DAGの最長パス

Question

DAGで最長のパスを見つけるために、私は2つのアルゴリズムを知っています。アルゴリズム1：トポロジカルソートを実行し、ソートの結果に対して動的プログラミングを使用します〜または〜アルゴリズム2：DFSを使用してDAG内のすべてのパスを列挙します。最長を記録します。DFSですべてのパスを列挙する方が、アルゴ1よりも複雑なようです。それは本当ですか？

Answer 1

2 番目のオプションは正しくありません。グラフがツリーまたはフォレストであり、ルートから開始しない限り、DFS は可能なすべてのパスを探索しません。私が知っている 2 番目のアルゴリズムは、重みを無効にして最短経路を見つけることですが、#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 を受け取ります。各アークは 1 つの変数 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 です。