C语言实现关键路径算法

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

#define MAX_SIZE 100

typedef struct Node { int id; // 结点的编号 int duration; // 结点的持续时间 int earliest; // 最早开始时间 int latest; // 最晚开始时间 int slack; // 松弛时间 int indegree; // 入度 int outdegree; // 出度 struct Node* next; // 下一个结点 } Node;

typedef struct Graph { Node* nodes[MAX_SIZE]; // 结点数组 int nodeCount; // 结点个数 int durationSum; // 整个项目的最短完成时间 } Graph;

Node* createNode(int id, int duration) { Node* node = (Node*)malloc(sizeof(Node)); node->id = id; node->duration = duration; node->earliest = 0; node->latest = 0; node->slack = 0; node->indegree = 0; node->outdegree = 0; node->next = NULL; return node; }

Graph* createGraph() { Graph* graph = (Graph*)malloc(sizeof(Graph)); graph->nodeCount = 0; graph->durationSum = 0; return graph; }

void addEdge(Graph* graph, int from, int to) { Node* fromNode = graph->nodes[from]; Node* toNode = graph->nodes[to];

// 创建一条从from结点到to结点的边
Node* edge = createNode(to, toNode->duration);

// 将边插入from结点的链表中
edge->next = fromNode->next;
fromNode->next = edge;

// 更新from结点和to结点的出度和入度
fromNode->outdegree++;
toNode->indegree++;

}

void calculateEarliest(Graph* graph, int nodeId) { Node* node = graph->nodes[nodeId]; Node* edge = node->next;

while (edge) {
    // 更新后续结点的最早开始时间
    Node* nextNode = graph->nodes[edge->id];
    nextNode->earliest = node->earliest + node->duration;

    // 更新整个项目的最短完成时间
    if (nextNode->earliest > graph->durationSum) {
        graph->durationSum = nextNode->earliest;
    }

    edge = edge->next;
}

}

void calculateLatest(Graph* graph, int nodeId) { Node* node = graph->nodes[nodeId]; Node* edge = node->next;

while (edge) {
    // 更新前驱结点的最晚开始时间
    Node* prevNode = graph->nodes[nodeId];
    int latest = node->latest - edge->duration;

    if (prevNode->latest == 0 || prevNode->latest > latest) {
        prevNode->latest = latest;
    }

    edge = edge->next;
}

}

void calculateSlack(Graph* graph) { for (int i = 0; i < graph->nodeCount; i++) { Node* node = graph->nodes[i]; node->slack = node->latest - node->earliest; } }

void findCriticalPath(Graph* graph) { // 计算每个结点的最早开始时间 for (int i = 0; i < graph->nodeCount; i++) { Node* node = graph->nodes[i]; if (node->indegree == 0) { node->earliest = 0; calculateEarliest(graph, node->id); } }

// 计算整个项目的最短完成时间
graph->durationSum = 0;
for (int i = 0; i < graph->nodeCount; i++) {
    Node* node = graph->nodes[i];
    if (node->outdegree == 0 && node->earliest + node->duration > graph->durationSum) {
        graph->durationSum = node->earliest + node->duration;
    }
}

// 计算每个结点的最晚开始时间
for (int i = graph->nodeCount - 1; i >= 0; i--) {
    Node* node = graph->nodes[i];
    if (node->outdegree == 0) {
        node->latest = graph->durationSum - node->duration;
        calculateLatest(graph, node->id);
    }
}

// 计算每个结点的松弛时间
calculateSlack(graph);

// 输出关键路径
printf('关键路径: ');
for (int i = 0; i < graph->nodeCount; i++) {
    Node* node = graph->nodes[i];
    if (node->slack == 0) {
        printf('%c ', 'A' + node->id);
    }
}
printf('\n');

// 输出整个项目的最短完成时间
printf('最短时间: %d7 days\n', graph->durationSum);

}

int main() { Graph* graph = createGraph(); Node* nodeA = createNode(0, 3); Node* nodeB = createNode(1, 2); Node* nodeC = createNode(2, 4); Node* nodeD = createNode(3, 5); Node* nodeE = createNode(4, 8); Node* nodeF = createNode(5, 3); Node* nodeG = createNode(6, 5); Node* nodeH = createNode(7, 10); Node* nodeI = createNode(8, 2);

graph->nodes[0] = nodeA;
graph->nodes[1] = nodeB;
graph->nodes[2] = nodeC;
graph->nodes[3] = nodeD;
graph->nodes[4] = nodeE;
graph->nodes[5] = nodeF;
graph->nodes[6] = nodeG;
graph->nodes[7] = nodeH;
graph->nodes[8] = nodeI;

graph->nodeCount = 9;

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 5);
addEdge(graph, 5, 6);
addEdge(graph, 4, 7);
addEdge(graph, 3, 8);
addEdge(graph, 6, 8);
addEdge(graph, 7, 8);

findCriticalPath(graph);

return 0;