방향 그래프에서 특정 노드부터 어떤 노드까지 도달하는데 가장 오래 걸리는 경로

→ 이는 곧 해당 노드를 시작할 수 있는 최단 경로가 된다

사이클이 있으면 안된다

• 예시
  • 하위 모듈들은 병렬적으로 수행되지만, 하위 모듈을 조립하여 사용해야 하는 상위 모듈은 하위 모듈들이 모두 수행되어야만 조립 가능

알고리즘

• Earliest Start Time
• Earliest Finish Time

시작노드로부터 해당 노드까지 현재까지 찾은 최장거리를 dis 배열로 구현한다.

• 초기엔 모두 0으로 유지한다
  • 최장경로를 구해야 하니까 !!

각 노드의 진입차수를 저장할 indegree 배열을 유지한다.

각 노드마다 이전에 어떤 경로를 지나왔는지 prev 배열을 유지한다.

위상 정렬과 과정은 비슷하다.

1. 시작 노드를 큐에 넣는다
2. 아래 과정을 큐가 빌 때까지 반복한다.
3. 큐에서 노드를 꺼낸다
   1. 꺼낸 노드에 연결된 노드들의 indegree를 1씩 감소시켜준다
   2. ( dis[node] + 다음 노드까지의 거리 ) 가 dis[next_node]보다 크다면 dis[next_node]의 값에 대입한다.
      1. 이 때 prev 경로를 갱신해준다.
      2. 만약 두 거리가 같다면 prev 경로에 append한다. 여러 최장 거리 중 하나를 선택해야 하기 떄문이다.
   3. indegree가 0이라면 다음 노드들을 큐에 넣어준다.

경로 역추적

dfs나 bfs로 prev[END] 경로를 추적한다