방향성이있는 비순환 그래프에서 '5'가장 중요한 경로를 찾는 방법은 무엇입니까?

Question

각 노드와 연관된 가중치를 갖는 방향성 비순환 그래프 (DAG)가 있습니다. 가장 큰 'n'(예 : 5)의 경로를 찾으면됩니다. 여기서 경로의 가중치는 노드의 모든 가중치의 합으로 정의됩니다. 이것을 어떻게 할 수 있습니까?

정확도는 바람직하지만 성능을 위해 희생 될 수 있습니다. 잠재적으로 그래프는 10,000 개 이상의 노드 및/또는 에지를 가질 수 있습니다.

편집 : 가중치는 0보다 크거나 같은 숫자입니다.

Answer 1

1. 그래프를 위상 정렬합니다.
2. 각 그래프의 노드를 n 요소 우선 순위 대기열 (min-heap)과 연관시킵니다.
3. 정렬 된 순서로 각 노드에 대해 우선 순위 대기열에서 경로 가중치를 팝하고 노드의 가중치를 추가하여 모든 자손에게 전달합니다. 노드가 상위 노드로부터 가중치를 받으면 관련 우선 순위 큐에 노드를 삽입해야합니다.
4. 각 리프 노드에 대해 우선 순위 큐에서 경로 가중치를 팝하고 노드의 가중치를 추가 한 다음 하나의 공통 우선 순위 큐에 삽입합니다. 마지막 노드가 처리 된 후,이 우선 순위 큐에는 'n'개의 가장 중요한 경로에 대한 가중치가 포함됩니다. 무게와 함께 포인터를 저장하면 이러한 경로를 복원 할 수 있습니다.