각 노드가 최대 2 개의 들어오는 가장자리와 2 개의 나가는 가장자리를 가지고있는 그래프에서 가장 긴 경로 찾기

Question

제목에서 말하자면 각 노드에 최대 2 개의 들어오는 가장자리와 2 개의 나가는 가장자리가있는 방향 그래프에서 가장 긴 경로를 찾아야한다고합니다. 나는 그 사실이 도움이되는지를 모른다. 그래프는 최대 10000 개의 노드를 가질 것이다. 그리고 노드 0에서 노드 'Exit'까지 10001이 될 가장 긴 경로를 찾아야합니다.

dijkstra를 코딩하려고했지만 작동하지 않았습니다.

미리 감사드립니다.

Answer 1

그래프를 전처리하고 규칙을 위반하는 노드에 연결된 가장자리의 가장자리 가중치를 매우 높게 설정 한 다음 가장 긴 경로를 반환하는 수정 된 버전의 dijkstra를 사용할 수 있습니다.