c语言编写求关键路径的程序

以下是用C语言实现关键路径算法的示例代码，代码实现的步骤和上面的步骤相同。

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

#define MAX_TASKS 100
#define MAX_PREDECESSORS 10
#define MAX_SUCCESSORS 10

typedef struct task {
    char name[20];
    int duration;
    struct task* pred[MAX_PREDECESSORS];
    int num_pred;
    struct task* succ[MAX_SUCCESSORS];
    int num_succ;
    int early_start;
    int late_start;
    int early_finish;
    int late_finish;
} Task;

Task* tasks[MAX_TASKS];
int num_tasks = 0;

void add_task(char* name, int duration) {
    Task* task = malloc(sizeof(Task));
    strcpy(task->name, name);
    task->duration = duration;
    task->num_pred = 0;
    task->num_succ = 0;
    tasks[num_tasks++] = task;
}

void add_dependency(char* pred_name, char* succ_name) {
    Task* pred = NULL;
    Task* succ = NULL;
    for (int i = 0; i < num_tasks; i++) {
        if (strcmp(tasks[i]->name, pred_name) == 0) {
            pred = tasks[i];
        }
        if (strcmp(tasks[i]->name, succ_name) == 0) {
            succ = tasks[i];
        }
    }
    if (pred == NULL || succ == NULL) {
        printf("Error: invalid task name\n");
        exit(1);
    }
    pred->succ[pred->num_succ++] = succ;
    succ->pred[succ->num_pred++] = pred;
}

void calculate_early_start_times() {
    for (int i = 0; i < num_tasks; i++) {
        Task* task = tasks[i];
        if (task->num_pred == 0) {
            task->early_start = 0;
        }
        else {
            int max_early_finish = 0;
            for (int j = 0; j < task->num_pred; j++) {
                Task* pred = task->pred[j];
                int early_finish = pred->early_start + pred->duration;
                if (early_finish > max_early_finish) {
                    max_early_finish = early_finish;
                }
            }
            task->early_start = max_early_finish;
        }
        task->early_finish = task->early_start + task->duration;
    }
}

void calculate_late_finish_times() {
    for (int i = num_tasks - 1; i >= 0; i--) {
        Task* task = tasks[i];
        if (task->num_succ == 0) {
            task->late_finish = task->early_finish;
        }
        else {
            int min_late_start = 1 << 30;
            for (int j = 0; j < task->num_succ; j++) {
                Task* succ = task->succ[j];
                int late_start = succ->late_finish - task->duration;
                if (late_start < min_late_start) {
                    min_late_start = late_start;
                }
            }
            task->late_finish = min_late_start + task->duration;
        }
        task->late_start = task->late_finish - task->duration;
    }
}

void find_critical_path() {
    printf("Critical Path:\n");
    for (int i = 0; i < num_tasks; i++) {
        Task* task = tasks[i];
        if (task->early_finish == task->late_finish) {
            printf("%s ", task->name);
        }
    }
    printf("\n");
}

int main() {
    add_task("A", 5);
    add_task("B", 3);
    add_task("C", 2);
    add_task("D", 4);
    add_task("E", 6);

    add_dependency("A", "B");
    add_dependency("A", "C");
    add_dependency("B", "D");
    add_dependency("C", "D");
    add_dependency("D", "E");

    calculate_early_start_times();
    calculate_late_finish_times();
    find_critical_path();

    return 0;
}

这段代码实现了一个简单的关键路径算法，可以用来计算一个有向无环图的关键路径。你可以将任务和依赖关系定义在 `main()` 函数中，也可以从文件或命令行参数中读取。