Directed Acyclical Graph에서 최대 경로를 찾는 알고리즘은 어떻게됩니까?

Question

어느 시점에서, A 노드에서 B 노드로 Directed Acyclical Graph의 최대 경로를 찾기 위해 복잡도 O (V + E)로 실행되는 알고리즘을 사용하고 있는데, 이는 플러드 채우기를 수행하여 어떤 노드가 노트 A에서 액세스 할 수 있으며 각 노드에있는 "부모"(다른 노드에서 오는 가장자리)의 수를 나타냅니다. 그런 다음 BFS를 수행하지만 이미 모든 "부모"를 사용했을 때 노드를 "활성화"합니다.

queue <int> a 
int paths[] ; //Number of paths that go to note i 
int edge[][] ; //Edges of a 
int mpath[] ; //max path from 0 to i (without counting the weight of i) 
int weight[] ; //weight of each node 

mpath[0] = 0 

a.push(0) 
while not empty(a) 
    for i in edge[a] 
     paths[i] += 1 
     a.push(i) 

while not empty(a) 
    for i in children[a] 
     mpath[i] = max(mpath[i], mpath[a] + weight[a]) ; 

     paths[i] -= 1 ; 
     if path[i] = 0 
      a.push(i) ; 

이 알고리즘에 특별한 이름이 있습니까? 나는 Informatics 교수에게 말했다. 그는 "DAG의 최대 경로"라고 불렀지 만, "나는 펜윅 나무로 첫 번째 문제를 풀었고, 두 번째는 Dijkstra로, 세 번째 문제는 최대 경로 ".

Answer 1

다른 언급 된 것처럼 단순히 "DAG의 최장 경로"입니다. 그러나 사용중인 기술은 실제로 topological sorting이고 dynamic programming입니다.

Answer 2

DAG에서 가장 긴 경로? DAG에 대해 언급해야합니다. 일반 그래프에서 가장 긴 경로를 찾는 것은 NP 완료입니다.

Answer 3

아마 일반적인 알고리즘이 아니기 때문입니다. DAG에서 경로를 찾아야 할 때는 정렬하고, 한 번 트래버스하고 가장 긴 경로를 유지해야합니다.