C 语言实现关键路径算法 - 代码示例与解析

#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_TASKS 100\n\n// 任务结构体\ntypedef struct {\n int id; // 任务编号\n int duration; // 工期\n int earliestStart; // 最早开始时间\n int latestStart; // 最晚开始时间\n int earliestFinish; // 最早完成时间\n int latestFinish; // 最晚完成时间\n int isCritical; // 是否为关键路径上的任务\n} Task;\n\n// 边结构体\ntypedef struct {\n int from; // 起始任务编号\n int to; // 目标任务编号\n} Edge;\n\nint main() {\n int n; // 任务个数\n int m; // 边个数\n\n printf("请输入任务个数和边个数：");\n scanf("%d %d", &n, &m);\n\n Task tasks[MAX_TASKS]; // 任务数组\n Edge edges[MAX_TASKS]; // 边数组\n\n // 初始化任务数组\n for (int i = 0; i < n; i++) {\n tasks[i].id = i + 1;\n tasks[i].duration = 0;\n tasks[i].earliestStart = 0;\n tasks[i].latestStart = 0;\n tasks[i].earliestFinish = 0;\n tasks[i].latestFinish = 0;\n tasks[i].isCritical = 0;\n }\n\n // 输入任务工期\n printf("请输入每个任务的工期：\n");\n for (int i = 0; i < n; i++) {\n printf("任务%d的工期：", i + 1);\n scanf("%d", &tasks[i].duration);\n }\n\n // 输入边信息\n printf("请输入每条边的起始任务和目标任务：\n");\n for (int i = 0; i < m; i++) {\n printf("边%d的起始任务和目标任务：", i + 1);\n scanf("%d %d", &edges[i].from, &edges[i].to);\n }\n\n // 计算最早开始时间和最早完成时间\n for (int i = 0; i < n; i++) {\n if (tasks[i].earliestStart == 0) {\n tasks[i].earliestStart = 1;\n }\n for (int j = 0; j < m; j++) {\n if (edges[j].to == tasks[i].id) {\n if (tasks[i].earliestStart + tasks[i].duration > tasks[edges[j].from - 1].earliestFinish) {\n tasks[edges[j].from - 1].earliestFinish = tasks[i].earliestStart + tasks[i].duration;\n }\n }\n }\n }\n\n // 计算最晚开始时间和最晚完成时间\n tasks[n - 1].latestStart = tasks[n - 1].earliestStart;\n tasks[n - 1].latestFinish = tasks[n - 1].earliestFinish;\n for (int i = n - 1; i >= 0; i--) {\n for (int j = 0; j < m; j++) {\n if (edges[j].from == tasks[i].id) {\n if (tasks[edges[j].to - 1].latestStart == 0) {\n tasks[edges[j].to - 1].latestStart = tasks[edges[j].to - 1].earliestStart;\n }\n if (tasks[i].latestStart > tasks[edges[j].to - 1].latestFinish - tasks[edges[j].to - 1].duration) {\n tasks[i].latestStart = tasks[edges[j].to - 1].latestFinish - tasks[edges[j].to - 1].duration;\n }\n }\n }\n tasks[i].latestFinish = tasks[i].latestStart + tasks[i].duration;\n }\n\n // 标记关键路径上的任务\n for (int i = 0; i < n; i++) {\n if (tasks[i].earliestStart == tasks[i].latestStart && tasks[i].earliestFinish == tasks[i].latestFinish) {\n tasks[i].isCritical = 1;\n }\n }\n\n // 输出关键路径上的任务\n printf("关键路径上的任务为：");\n for (int i = 0; i < n; i++) {\n if (tasks[i].isCritical) {\n printf("%d ", tasks[i].id);\n }\n }\n\n return 0;\n}\n请输入任务个数和边个数：5 6\n请输入每个任务的工期：\n任务1的工期：3\n任务2的工期：4\n任务3的工期：2\n任务4的工期：5\n任务5的工期：3\n请输入每条边的起始任务和目标任务：\n边1的起始任务和目标任务：1 2\n边2的起始任务和目标任务：1 3\n边3的起始任务和目标任务：2 4\n边4的起始任务和目标任务：3 4\n边5的起始任务和目标任务：3 5\n边6的起始任务和目标任务：4 5\n关键路径上的任务为：1 3 4 5