DAG内で最長のパス

Question

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

Answer 1

2番目のオプションが正しくありません。DFSは、グラフがツリーまたはフォレストで、ルートから開始しない限り、すべての可能なパスを探索しません。私が知っている2番目のアルゴリズムは、ウェイトを無効にして最短経路を見つけることですが、＃1としてリストアップしたtop sort + DP algorithmよりもいくらか遅いです。 "DFS" を使用してDAGで

Answer 2

列挙すべてのパス：

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は必要。 アルゴリズム：MAX_PATHは、すべてのノードが処理されたエッジの中で一番高い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. 

各アークは、一つの変数Eを保持DAG G. をとります。