AOV/AOE 네트워크 (Activity on Vertex/Edge)

이번 포스트에서는 알고리즘 중의 AOV/AOE 네트워크에 대해 다루겠다.

 

AOV 네트워크란?

:  AOV는 Activity On Vertex의 약자이다. 즉, 정점이 Activity, 작업을 나타내고, 간선이 작업간의 우선순위 관계를 나타내는 방향 그래프이다.

 

AOV 동작 과정

AOV

1. 스택 [0], 위상 순서 []
2. 스택 [3, 2, 1], 위상 순서 [0] (1, 2, 3번 노드의 선행 노드 0이 사라졌으므로 스택에 저장)
3. 스택 [2, 1], 위상 순서 [0, 3]
4. 스택 [5, 1], 위상 순서 [0, 3, 2]
5. 스택 [1], 위상 순서 [0, 3, 2, 5]
6. 스택 [4], 위상 순서  [0, 3, 2, 5, 1]
7. 스택 [], 위상 순서 [0, 3, 2, 5, 1, 4]

---

AOE 네트워크란?

: AOE는 Activity On Edge 의 약자로, 간선은 작업에 걸리는 시간을 가직 있다. AOE 네트워크의 목표는 작업들을 수행하는 데 걸리는 최단시간을 구하는 것이다.

 

AOE 동작 과정

• Earlist

Earliest	0	1	2	3	4	5	6	7	8	Stack
initial	0	0	0	0	0	0	0	0	0	[0]
output V0	0	6	4	5	0	0	0	0	0	[3, 2, 1]
output V3	0	6	4	5	0	7(5+2)	0	0	0	[5, 2, 1]
output V5	0	6	4	5	0	7	0	11	0	[2, 1]
output V2	0	6	4	5	5	7	0	11	0	[1]
output V1	0	6	4	5	7	7	0	11	0	[4]
output V4	0	6	4	5	7	7	15	13	0	[7, 6]
output V7	0	6	4	5	7	7	15	13	17	[6]
output V8	0	6	4	5	7	7	15	13	17	[8]

• Latest

Latese	0	1	2	3	4	5	6	7	8	Stack
initial	17	17	17	17	17	17	17	17	17	[8]
output V8	17	17	17	17	17	17	15	13	17	[7, 6]
output V7	17	17	17	17	7	9	15	13	17	[5, 6]
output V5	17	17	17	7	7	9	15	13	17	[3, 6]
output V3	2	17	17	7	7	9	15	13	17	[6]
output V6	2	17	17	7	7	9	15	13	17	[4]
output V4	2	6	6	7	7	9	15	13	17	[2, 1]
output V2	2	6	6	7	7	9	15	13	17	[1]
output V1	0	6	6	7	7	9	15	13	17	[0]