39. AOE

AOE란?

AOV와는 다르게 간선이 작업을 표현하며, 가중치는 작업의 소요 시간을 의미한다.

정점은 작업의 완료를 나타내는 사건을 의미한다.

AOE 네트워크는 선후행 관계를 가진 작업 또는 활동들을 그래프로 표현한 것이다.

작업 간의 선후행 관계와 소요 시간을 통해 프로젝트의 전체 소요 시간을 계산할 수 있다.

 

AOE 네트워크는 프로젝트 관리에서 크리티컬 패스를 분석하는 데에 사용된다.

크리티컬 패스는 전체 프로젝트 소요 시간을 결정하는 가장 긴  경로를 의미하며, 작업등 간의 선후행 관계와 소요 시간을 고려하여 도출된다. 크리티컬 패스 상의 작업들은 프로젝트 완료 기한을 결정하는 핵심적인 작업들로 간주된다.

---

AOE 구현

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100

// 그래프의 정점을 나타내는 구조체
typedef struct Vertex {
    int id;
} Vertex;

// 그래프의 인접 행렬
int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {0};

// 그래프의 정점을 저장하는 배열
Vertex vertices[MAX_VERTICES];

// 정점을 추가하는 함수
void addVertex(int id) {
    vertices[id].id = id;
}

// 간선을 추가하는 함수
void addEdge(int start, int end, int weight) {
    adjMatrix[start][end] = weight;
}

// 크리티컬 패스를 계산하는 함수
void computeCriticalPath(int numVertices) {
    int earliestStart[MAX_VERTICES] = {0}; // 각 정점의 최소 시작 시간
    int latestFinish[MAX_VERTICES] = {0}; // 각 정점의 최대 완료 시간

    // 모든 정점의 최소 시작 시간 계산
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            if (adjMatrix[j][i] > 0) {
                int candidate = earliestStart[j] + adjMatrix[j][i];
                if (candidate > earliestStart[i]) {
                    earliestStart[i] = candidate;
                }
            }
        }
    }

    // 모든 정점의 최대 완료 시간 계산
    latestFinish[numVertices - 1] = earliestStart[numVertices - 1];
    for (int i = numVertices - 2; i >= 0; i--) {
        for (int j = i + 1; j < numVertices; j++) {
            if (adjMatrix[i][j] > 0) {
                int candidate = latestFinish[j] - adjMatrix[i][j];
                if (latestFinish[i] == 0 || candidate < latestFinish[i]) {
                    latestFinish[i] = candidate;
                }
            }
        }
    }

    // 크리티컬 패스 상의 작업들 출력
    printf("Critical Path: ");
    for (int i = 0; i < numVertices; i++) {
        if (earliestStart[i] == latestFinish[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");

    // 전체 프로젝트 소요 시간 출력
    printf("Total Duration: %d\n", earliestStart[numVertices - 1]);
}

int main() {
    int numVertices, numEdges;
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);

    // 그래프 초기화
    for (int i = 0; i < numVertices; i++) {
        addVertex(i);
    }

    printf("Enter the number of edges: ");
    scanf("%d", &numEdges);

    // 간선 추가
    printf("Enter edges and weights:\n");
    for (int i = 0; i < numEdges; i++) {
        int start, end, weight;
        scanf("%d %d %d", &start, &end, &weight);
        addEdge(start, end, weight);
    }

    // 크리티컬 패스 계산
    computeCriticalPath(numVertices);

    return 0;
}