크리티컬 패스 분석법 - 위키백과, 우리 모두의 백과사전
AOE네트워크 (혹은 DAG)에서 시작부터 끝까지 가는 경로중 가장 긴 경로를 찾는 알고리즘이다.
참고블로그
AOE네트워크에서 다루는 간단한 개념을 집고 넘어간다.
AOE Network는 Edge에 Process Time이 저장되고 Node에 Process Status가 저장된다. 이 Network의 최장 경로를 Critical Path라고 한다. Critical Path의 길이를 단축시킴으로서 전체 수행시간을 단축할 수 있다.
i, j노드를 연결하는 간선 k = (i, j)가 있다고 해보자.
노드 i가 실행될 수 있는 가장 빠른시간을 나타낸다. i가 실행되기 위해서는 i로 들어오는 모든 간선이 완료되어야 한다. 따라서 그 간선들 중 앞선 노드의 Earliest와 가중치를 더해 가장 오랜시간이 걸리는 값이 earliest[i]가 된다.
간선 k가 실행되는 가장 빠른시간이다.
노드 i가 실행해도 되는 가장 늦은시간을 나타낸다. 간단히 말하면 전체 그래프의 수행시간을 늘리지 않는 조건하에 가장 느리게 시작해도 되는 시간이다.
i → j로 가는 간선이 있다고 해보자. j로 들어오는 모든 간선중에서 i로부터의 간선이 가장 느린 간선이 아니라면 i는 그만큼 늦게 시작을 해도 된다.
따라서 i에서 연결된 모든 노드들의 latest에 그 weight를 뺀 값들의 최솟값이 latest[i]가 된다.