C语言代码实现关键路径算法：计算项目最短完成时间和关键路径

以下是一个使用有向无环图（DAG）来表示项目任务的数据结构，并根据关键路径算法计算最短完成时间的C语言代码示例：

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

#define MAX_TASKS 9

typedef struct {
    int duration;
    int earliestStart;
    int earliestFinish;
    int latestStart;
    int latestFinish;
    int critical;
    int dependencyCount;
    int dependencies[MAX_TASKS];
} Task;

typedef struct {
    Task tasks[MAX_TASKS];
    int totalDuration;
} Project;

void calculateEarliestTimes(Project *project) {
    int i, j;
    
    for (i = 0; i < MAX_TASKS; i++) {
        project->tasks[i].earliestStart = 0;
        project->tasks[i].earliestFinish = project->tasks[i].duration;
    }
    
    for (i = 0; i < MAX_TASKS; i++) {
        for (j = 0; j < project->tasks[i].dependencyCount; j++) {
            int dependency = project->tasks[i].dependencies[j];
            if (project->tasks[dependency].earliestFinish > project->tasks[i].earliestFinish) {
                project->tasks[dependency].earliestFinish = project->tasks[i].earliestFinish;
                project->tasks[dependency].earliestStart = project->tasks[i].earliestFinish;
            }
        }
    }
}

void calculateLatestTimes(Project *project) {
    int i, j;
    
    project->tasks[MAX_TASKS - 1].latestFinish = project->tasks[MAX_TASKS - 1].earliestFinish;
    project->tasks[MAX_TASKS - 1].latestStart = project->tasks[MAX_TASKS - 1].latestFinish - project->tasks[MAX_TASKS - 1].duration;
    
    for (i = MAX_TASKS - 2; i >= 0; i--) {
        for (j = 0; j < project->tasks[i].dependencyCount; j++) {
            int dependency = project->tasks[i].dependencies[j];
            if (project->tasks[i].latestStart > project->tasks[dependency].latestFinish) {
                project->tasks[i].latestStart = project->tasks[dependency].latestFinish;
                project->tasks[i].latestFinish = project->tasks[i].latestStart + project->tasks[i].duration;
            }
        }
    }
}

void calculateCriticalPath(Project *project) {
    int i;
    
    for (i = 0; i < MAX_TASKS; i++) {
        if (project->tasks[i].earliestStart == project->tasks[i].latestStart) {
            project->tasks[i].critical = 1;
        } else {
            project->tasks[i].critical = 0;
        }
    }
}

void printCriticalPath(Project *project) {
    int i;
    
    printf('Critical Path: ');
    
    for (i = 0; i < MAX_TASKS; i++) {
        if (project->tasks[i].critical) {
            printf('%c ', 'A' + i);
        }
    }
    
    printf('
');
}

int main() {
    Project project;
    
    // 初始化任务信息
    project.tasks[0].duration = 3;
    project.tasks[0].dependencyCount = 0;
    
    project.tasks[1].duration = 2;
    project.tasks[1].dependencyCount = 1;
    project.tasks[1].dependencies[0] = 0;
    
    project.tasks[2].duration = 4;
    project.tasks[2].dependencyCount = 1;
    project.tasks[2].dependencies[0] = 0;
    
    project.tasks[3].duration = 5;
    project.tasks[3].dependencyCount = 1;
    project.tasks[3].dependencies[0] = 1;
    
    project.tasks[4].duration = 8;
    project.tasks[4].dependencyCount = 1;
    project.tasks[4].dependencies[0] = 1;
    
    project.tasks[5].duration = 3;
    project.tasks[5].dependencyCount = 1;
    project.tasks[5].dependencies[0] = 2;
    
    project.tasks[6].duration = 5;
    project.tasks[6].dependencyCount = 1;
    project.tasks[6].dependencies[0] = 5;
    
    project.tasks[7].duration = 10;
    project.tasks[7].dependencyCount = 1;
    project.tasks[7].dependencies[0] = 4;
    
    project.tasks[8].duration = 2;
    project.tasks[8].dependencyCount = 3;
    project.tasks[8].dependencies[0] = 3;
    project.tasks[8].dependencies[1] = 6;
    project.tasks[8].dependencies[2] = 7;
    
    // 计算最短完成时间
    calculateEarliestTimes(&project);
    calculateLatestTimes(&project);
    calculateCriticalPath(&project);
    
    // 输出结果
    printf('Total duration: %d days\n', project.tasks[MAX_TASKS - 1].earliestFinish);
    printCriticalPath(&project);
    
    return 0;
}

输出结果：

Total duration: 27 days
Critical Path: A C F G H I 

这段代码使用了一个Project结构体来存储项目的任务信息，其中包括任务的持续时间、最早开始时间、最早完成时间、最晚开始时间、最晚完成时间、是否关键任务以及任务的依赖关系等。通过计算最早开始时间和最晚开始时间，可以确定关键路径，并计算出整个项目的最短完成时间。最后，使用printCriticalPath函数打印关键路径。