1. 개요

- AOE 네트워크는 그래프의 일종으로, 간선에 가중치가 있는 방향그래프이다. 간선은 작업, 간선의 가중치는 작업 수행 시간, 간선의 방향은 사건의 선후관계를 나타내며, 간선의 끝부분에 있는 노드는 그 작업의 수행의 결과로서 도달하게 되는 사건을 의미한다. 어떤 사건도 그 선행 작업이 종료되기 전에는 일어날 수 없다. 

- 수개의 작업을 동시에 수행할 수 있지만, 모든 작업을 다 수행해 최종 사건에 도달하기까지 걸리는 시간은 아무리 빨라도 시작 노드부터 끝 노드까지의 최장경로길이_(이를 임계경로라 한다)_다.

2. 임계경로를 구하는 알고리즘

1) 개념

- 각 노드 \(i\)에 대해 함수 e(\(i\))와 l(\(i\))의 값을 구해둔 후, 이를 이용해 모든 간선(작업)의 ‘임계도’를 구한다.

함수명 정의
e(\(i\)) 노드 \(i\)에 도달하기 위해 필요한 최소시간
l(\(i\)) 전체 작업이 임계경로 시간 안에 수행되기 위해 노드 \(i\)에서 출발해야 하는 최대 시간
간선 (\(i\), \(j\))의 임계도  l(\(i\)) - e(\(i\)) + W(\(i\), \(j\))

- 모든 간선에 대해 임계도를 구해 보면, 어떤 간선의 임계도는 0인 경우가 있다. 이 간선들이 임계경로를 구성하는 간선이다.

2) e(\(i\))를 구하는 알고리즘

-위상정렬을 수행하면서, 현재 도달한 노드 \(i\)와 연결된 모든 후행 노드 \(k\)에 대하여 e(\(k\)) = max( e(\(k\)), e(\(i\)) + W(\(i\), \(k\)) ) 값을 계산함으로써 e(\(i\)) 값을 구할 수 있다.

3) l(\(i\))를 구하는 알고리즘

- 일단 위상정렬을 통해 임계경로의 길이를 구한 후, l(\(i\)) 배열을 이 값으로 초기화한다.

- 그 다음, 모든 간선의 방향을 반대로 바꾸고 끝 정점에서부터 거꾸로 위상정렬을 수행한다. 이때 현재 도달한 노드 \(i\)와 연결된 모든 후행 노드 \(k\)에 대하여 l(\(k\)) = max( l(\(k\)), l(\(i\)) - W(\(i\), \(k\)) ) 값을 계산함으로써 l(\(i\)) 값을 구할 수 있다.