C++ 关键路径算法实现：示例代码及优化

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

// 定义活动的结构体 typedef struct { char name; int duration; int earliestStart; int latestStart; int critical; int numOfPredecessors; char *predecessors; } Activity;

// 计算关键路径的函数 void calculateCriticalPath(Activity *activities, int numActivities) { int i, j, k; int maxDuration = 0;

// 初始化最早开始时间和最晚开始时间
for (i = 0; i < numActivities; i++) {
    activities[i].earliestStart = 0;
    activities[i].latestStart = INT_MAX;
}

// 计算每个活动的最早开始时间
for (i = 0; i < numActivities; i++) {
    for (j = 0; j < activities[i].numOfPredecessors; j++) {
        k = activities[i].predecessors[j] - 'A';
        if (activities[k].duration + activities[k].earliestStart > activities[i].earliestStart) {
            activities[i].earliestStart = activities[k].duration + activities[k].earliestStart;
        }
    }
}

// 计算项目的最长时间
for (i = 0; i < numActivities; i++) {
    if (activities[i].duration + activities[i].earliestStart > maxDuration) {
        maxDuration = activities[i].duration + activities[i].earliestStart;
    }
}

// 计算每个活动的最晚开始时间
for (i = numActivities - 1; i >= 0; i--) {
    for (j = 0; j < activities[i].numOfPredecessors; j++) {
        k = activities[i].predecessors[j] - 'A';
        if (activities[i].latestStart - activities[i].duration < activities[k].latestStart) {
            activities[k].latestStart = activities[i].latestStart - activities[i].duration;
        }
    }
}

// 标记关键路径
for (i = 0; i < numActivities; i++) {
    if (activities[i].earliestStart == activities[i].latestStart) {
        activities[i].critical = 1;
    } else {
        activities[i].critical = 0;
    }
}

// 输出关键路径
printf("关键路径为：");
for (i = 0; i < numActivities; i++) {
    if (activities[i].critical) {
        printf("%c ", activities[i].name);
    }
}
printf("\n");

// 输出项目最迟开始时间
printf("项目最迟开始时间为：%d\n", maxDuration);

}

int main() { int numActivities = 9; Activity activities[numActivities];

// 初始化活动列表
activities[0].name = 'A';
activities[0].duration = 3;
activities[0].numOfPredecessors = 0;

activities[1].name = 'B';
activities[1].duration = 2;
activities[1].numOfPredecessors = 1;
activities[1].predecessors = (char *)malloc(sizeof(char));
*(activities[1].predecessors) = 'A';

activities[2].name = 'C';
activities[2].duration = 4;
activities[2].numOfPredecessors = 1;
activities[2].predecessors = (char *)malloc(sizeof(char));
*(activities[2].predecessors) = 'A';

activities[3].name = 'D';
activities[3].duration = 5;
activities[3].numOfPredecessors = 1;
activities[3].predecessors = (char *)malloc(sizeof(char));
*(activities[3].predecessors) = 'B';

activities[4].name = 'E';
activities[4].duration = 8;
activities[4].numOfPredecessors = 1;
activities[4].predecessors = (char *)malloc(sizeof(char));
*(activities[4].predecessors) = 'B';

activities[5].name = 'F';
activities[5].duration = 3;
activities[5].numOfPredecessors = 1;
activities[5].predecessors = (char *)malloc(sizeof(char));
*(activities[5].predecessors) = 'C';

activities[6].name = 'G';
activities[6].duration = 5;
activities[6].numOfPredecessors = 1;
activities[6].predecessors = (char *)malloc(sizeof(char));
*(activities[6].predecessors) = 'F';

activities[7].name = 'H';
activities[7].duration = 10;
activities[7].numOfPredecessors = 1;
activities[7].predecessors = (char *)malloc(sizeof(char));
*(activities[7].predecessors) = 'E';

activities[8].name = 'I';
activities[8].duration = 2;
activities[8].numOfPredecessors = 3;
activities[8].predecessors = (char *)malloc(3 * sizeof(char));
activities[8].predecessors[0] = 'D';
activities[8].predecessors[1] = 'G';
activities[8].predecessors[2] = 'H';

calculateCriticalPath(activities, numActivities);

return 0;

}