关键路径算法

关键路径算法（Critical Path Method，CPM）是一种用于项目管理的算法，用于确定项目中最长的路径，即关键路径，以及各个任务的最早开始时间和最晚开始时间。以下是一个关键路径算法的Java代码示例：

import java.util.*;

class Task {
    String name;
    int duration;
    List<Task> dependencies;

    Task(String name, int duration) {
        this.name = name;
        this.duration = duration;
        this.dependencies = new ArrayList<>();
    }

    void addDependency(Task dependency) {
        dependencies.add(dependency);
    }
}

public class CriticalPathMethod {

    public static void calculateCriticalPath(List<Task> tasks) {
        Map<Task, Integer> earliestStartTimes = new HashMap<>();
        Map<Task, Integer> latestStartTimes = new HashMap<>();

        // 计算最早开始时间
        for (Task task : tasks) {
            int earliestStartTime = 0;
            for (Task dependency : task.dependencies) {
                earliestStartTime = Math.max(earliestStartTime, earliestStartTimes.get(dependency) + dependency.duration);
            }
            earliestStartTimes.put(task, earliestStartTime);
        }

        // 计算最晚开始时间
        int projectDuration = 0;
        for (Task task : tasks) {
            projectDuration = Math.max(projectDuration, earliestStartTimes.get(task) + task.duration);
        }
        for (Task task : tasks) {
            latestStartTimes.put(task, projectDuration - task.duration);
        }

        // 计算关键路径
        System.out.println("Critical Path:");
        for (Task task : tasks) {
            if (earliestStartTimes.get(task).equals(latestStartTimes.get(task))) {
                System.out.println(task.name);
            }
        }
    }

    public static void main(String[] args) {
        Task A = new Task("A", 5);
        Task B = new Task("B", 3);
        Task C = new Task("C", 2);
        Task D = new Task("D", 4);
        Task E = new Task("E", 6);

        B.addDependency(A);
        C.addDependency(A);
        D.addDependency(B);
        D.addDependency(C);
        E.addDependency(D);

        List<Task> tasks = new ArrayList<>(Arrays.asList(A, B, C, D, E));

        calculateCriticalPath(tasks);
    }
}

在这个示例中，我们使用关键路径算法来计算一个简单项目的关键路径。Task 类表示任务，其中包含任务名称、持续时间和依赖关系。calculateCriticalPath 方法计算每个任务的最早开始时间和最晚开始时间，并根据最早开始时间和最晚开始时间的差异来确定关键路径。

这个示例是一个简化的关键路径算法实现，实际应用中可能需要考虑更多的细节和优化。