关键路径算法c++实现

关键路径算法，又称关键路径分析，是一种用于确定项目中关键任务的方法。关键路径是指在项目完成时间不变的情况下，导致项目完成时间延长的任务序列。

以下是C++实现关键路径算法的代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
    int to, weight;
};

vector<int> topological_sort(vector<vector<Edge>>& graph) {
    vector<int> in_degree(graph.size(), 0);
    for (int i = 0; i < graph.size(); ++i) {
        for (auto& e : graph[i]) {
            in_degree[e.to]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < in_degree.size(); ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        for (auto& e : graph[u]) {
            in_degree[e.to]--;
            if (in_degree[e.to] == 0) {
                q.push(e.to);
            }
        }
    }

    return result;
}

void critical_path(vector<vector<Edge>>& graph) {
    vector<int> topo_order = topological_sort(graph);
    vector<int> earliest_time(graph.size(), 0);
    for (int u : topo_order) {
        for (auto& e : graph[u]) {
            earliest_time[e.to] = max(earliest_time[e.to], earliest_time[u] + e.weight);
        }
    }

    vector<int> latest_time(graph.size(), earliest_time.back());
    for (int i = topo_order.size() - 1; i >= 0; --i) {
        int u = topo_order[i];
        for (auto& e : graph[u]) {
            latest_time[u] = min(latest_time[u], latest_time[e.to] - e.weight);
        }
    }

    cout << "Critical path:" << endl;
    for (int u = 0; u < graph.size(); ++u) {
        for (auto& e : graph[u]) {
            int task_time = earliest_time[u] + e.weight + latest_time[e.to] - earliest_time.back();
            if (task_time == 0) {
                cout << u << " -> " << e.to << endl;
            }
        }
    }
}

int main() {
    // 举例：一个项目的任务时间如下所示
    // (0) -> (1) -> (2) -> (3) -> (4)
    //   2     3     1     4     3
    vector<vector<Edge>> graph(5);
    graph[0].push_back({1, 2});
    graph[1].push_back({2, 3});
    graph[2].push_back({3, 1});
    graph[3].push_back({4, 4});

    critical_path(graph);

    return 0;
}

输出：

Critical path:
0 -> 1
1 -> 2
2 -> 3
3 -> 4