DAG에서 가장 높은 점수로 경로를 찾는 것

Question

각 노드가 할당 된 정수 점수를 갖는 지시 된 acycycl 그래프가 있는지, 가장 높은 누적 점수로 시작 및 끝점에서 경로를 찾는 빠른 방법은 무엇입니까?나는 끝에서 시작하여 역방향으로 그래프를 실행하는 DFS 접근법을 생각하고 각 노드에서 가장 좋은 누적 점수를 얻을 수 있습니다.결과를 인쇄하려면 첫 번째 노드에서 시작하여 가장 높은 누적 점수로 다음 노드를 탐험히 선택합니다.그러나 나는 우리가 비우호적 인 그래프를 받으면 많은 시간을 횡단 할 수있는 것처럼 이것이 가장 좋은 방법이라고 생각하지 않는다.이렇게하는 더 좋은 방법이 있습니까?

Answer 1

힌트 : 토폴로지 순서를 찾고, 각 꼭지점 $ v $ , 최고 점수가있는 경로를 계산 (점수) $ V $ 을 종료합니다.