[ 알고리즘 ] 14. DFS 활용 - Critical Path ( 최장 경로 )

DAG에서 Dependency가 있는 그래프에서

각각의 Task의 Duration이 정해져있다.

 

 

외출하는 데 필요한 작업들은 다음과 같다.

하지만 이 중에서도 순서가 중요함.

 

 

 

Time Complexity는 세타 ( Vertex + Edge )

 

우리가 각 노드에 대해서 알아야 하는 건

- Earliest start time ( EST )     
    =  앞에 완료되어야 하는 애가 끝난 시간

 

- Earliest finish time ( EFT ) 이다.

    = EST + Duration 

 

 

 

EST 를 계산하는 건

Dependency가 있는 노드의 앞에 완료되어야 하는 작업이 있다면

그 작업 중에 가장 Max로 끝나는 시간으로 한다.

 

 

Vertex가 Weight에 영향을 받는다는 개념으로 풀어야 한다.

방향을 우리가 생각하는 거에서 Reverse를 해야함.

 

+가장 마지막에 Done이라는 Vertex를 추가한다.

 

 

 

해당 노드의 Duration이 자신에게 오는 Edge의 Weight로 들어간다.

 

---

 

문제 푸는 법

BackTraking 하려고 할 때

w 노드가 끝난 시간이, 지금까지 v노드를 시작할 수 있다고 알려진 시간보다 크다면

v가 시작하는 시간은 현재 w가 끝난 시간으로 하고

v의 Critical dep은 w로 한다. (현재까지 얘가 가장 큰 값이니까) 

 

 

= v가 3에 시작하려고 했는데, 이제보니 w가 7에 끝나면

   v가 7에 시작한다

   그리고 v로 오는 것들 중에 가장 오래 걸리는 놈을 w로 설정한다.

 

 

그런 다음에 v의 끝나는 시간은 , est[v]에 v의 duration을 더하면 된다.

 

 

 

처음 done에서 출발할 때는 est =0 으로 가고, Backtrack을 할 때부터 업데이트하면서 온다.

 

 

 

9번 노드 est + duration  = 0

 

 

1번 노드 est = max (현재 값 , 새로 들어온 값)  = 0 , 9의 eft = 0

eft = est + duration = 3

 

2번까지 backtrack

 

 

2번 backtrack 이후에는 다시 갈 수 있는 길이 있으니 DFS를 진행한다.

쭉 가는데 9번 노드의 eft는 이미 구했기 때문에 그걸 가지고 8을 계산한다.

 

...

 

---

---

연습문제

 

 

 

(출처)

한동대학교 용환기교수님 - 알고리즘