关键路径计算算法：C语言实现

#include <stdio.h>\n#include <stdlib.h>\n#include <limits.h>\n\n// 定义活动的结构体\ntypedef struct {\n char name; \n int duration; \n int earliestStart; \n int latestStart; \n int critical; \n int numOfPredecessors; \n char *predecessors; \n} Activity; \n\n// 计算关键路径的函数\nvoid calculateCriticalPath(Activity *activities, int numActivities) { \n int i, j, k; \n int maxDuration = 0; \n char criticalPath[numActivities]; \n int pathIndex = 0; \n \n // 初始化最早开始时间和最晚开始时间 \n for (i = 0; i < numActivities; i++) { \n activities[i].earliestStart = 0; \n activities[i].latestStart = INT_MAX; \n } \n \n // 计算每个活动的最早开始时间 \n for (i = 0; i < numActivities; i++) { \n for (j = 0; j < activities[i].numOfPredecessors; j++) { \n k = activities[i].predecessors[j] - 'A'; \n if (activities[k].duration + activities[k].earliestStart > activities[i].earliestStart) { \n activities[i].earliestStart = activities[k].duration + activities[k].earliestStart; \n } \n } \n } \n \n // 计算项目的最长时间 \n for (i = 0; i < numActivities; i++) { \n if (activities[i].duration + activities[i].earliestStart > maxDuration) { \n maxDuration = activities[i].duration + activities[i].earliestStart; \n } \n } \n \n // 计算每个活动的最晚开始时间 \n for (i = numActivities - 1; i >= 0; i--) { \n for (j = 0; j < activities[i].numOfPredecessors; j++) { \n k = activities[i].predecessors[j] - 'A'; \n if (activities[i].latestStart - activities[i].duration < activities[k].latestStart) { \n activities[k].latestStart = activities[i].latestStart - activities[i].duration; \n } \n } \n } \n \n // 标记关键路径 \n for (i = 0; i < numActivities; i++) { \n if (activities[i].earliestStart == activities[i].latestStart) { \n activities[i].critical = 1; \n } else { \n activities[i].critical = 0; \n } \n if (activities[i].critical) { \n criticalPath[pathIndex++] = activities[i].name; \n } \n } \n \n // 输出关键路径 \n printf("关键路径为："); \n for (i = 0; i < pathIndex; i++) { \n printf("%c ", criticalPath[i]); \n } \n printf("\n"); \n \n // 输出项目最迟开始时间 \n printf("项目最迟开始时间为：%d\n", maxDuration); \n} \n\nint main() { \n int numActivities = 9; \n Activity activities[numActivities]; \n int i; \n \n // 初始化活动列表 \n activities[0].name = 'A'; \n activities[0].duration = 3; \n activities[0].numOfPredecessors = 0; \n \n activities[1].name = 'B'; \n activities[1].duration = 2; \n activities[1].numOfPredecessors = 1; \n activities[1].predecessors = (char *)malloc(sizeof(char)); \n *(activities[1].predecessors) = 'A'; \n \n activities[2].name = 'C'; \n activities[2].duration = 4; \n activities[2].numOfPredecessors = 1; \n activities[2].predecessors = (char *)malloc(sizeof(char)); \n *(activities[2].predecessors) = 'A'; \n \n activities[3].name = 'D'; \n activities[3].duration = 5; \n activities[3].numOfPredecessors = 1; \n activities[3].predecessors = (char *)malloc(sizeof(char)); \n *(activities[3].predecessors) = 'B'; \n \n activities[4].name = 'E'; \n activities[4].duration = 8; \n activities[4].numOfPredecessors = 1; \n activities[4].predecessors = (char *)malloc(sizeof(char)); \n *(activities[4].predecessors) = 'B'; \n \n activities[5].name = 'F'; \n activities[5].duration = 3; \n activities[5].numOfPredecessors = 1; \n activities[5].predecessors = (char *)malloc(sizeof(char)); \n *(activities[5].predecessors) = 'C'; \n \n activities[6].name = 'G'; \n activities[6].duration = 5; \n activities[6].numOfPredecessors = 1; \n activities[6].predecessors = (char *)malloc(sizeof(char)); \n *(activities[6].predecessors) = 'F'; \n \n activities[7].name = 'H'; \n activities[7].duration = 10; \n activities[7].numOfPredecessors = 1; \n activities[7].predecessors = (char *)malloc(sizeof(char)); \n *(activities[7].predecessors) = 'E'; \n \n activities[8].name = 'I'; \n activities[8].duration = 2; \n activities[8].numOfPredecessors = 3; \n activities[8].predecessors = (char *)malloc(3 * sizeof(char)); \n *(activities[8].predecessors) = 'D'; \n *(activities[8].predecessors + 1) = 'G'; \n *(activities[8].predecessors + 2) = 'H'; \n \n calculateCriticalPath(activities, numActivities); \n \n return 0; \n}