图的关键路径算法

关键路径算法（Critical Path Method, CPM）是一种用于项目管理和调度的技术，通过分析项目任务的最早开始时间、最晚完成时间和总时差，找出项目中关键的任务路径。这条关键路径决定了项目的最短完成时间，因为关键路径上的每个任务都不能被延迟，否则整个项目会被延迟。

关键路径算法的步骤

1. 构建有向图：将项目中的任务和任务间的依赖关系表示为有向图，节点表示任务，边表示依赖关系。

2. 计算任务的最早开始时间和最早完成时间：

   • 最早开始时间（ES, Earliest Start Time）：某任务可以开始的最早时间。
   • 最早完成时间（EF, Earliest Finish Time）：某任务可以完成的最早时间，EF = ES + 任务持续时间。

3. 计算任务的最晚开始时间和最晚完成时间：

   • 最晚完成时间（LF, Latest Finish Time）：某任务必须完成的最晚时间，不会延误项目。
   • 最晚开始时间（LS, Latest Start Time）：某任务必须开始的最晚时间，LS = LF - 任务持续时间。

4. 计算总时差和自由时差：

   • 总时差（Total Float, TF）：某任务可以延迟的时间，TF = LF - EF 或 TF = LS - ES。
   • 自由时差（Free Float, FF）：某任务可以延迟的时间，不会延误后续任务，FF = min(ES of next tasks) - EF of current task。

5. 找出关键路径：关键路径上的任务总时差为 0，连接这些任务的路径就是关键路径。

示例与实现

考虑一个简单的项目，有 6 个任务（A、B、C、D、E、F），以及它们的持续时间和依赖关系如下：

• 任务 A：持续时间 3 天
• 任务 B：持续时间 2 天，依赖于任务 A
• 任务 C：持续时间 4 天，依赖于任务 A
• 任务 D：持续时间 2 天，依赖于任务 B
• 任务 E：持续时间 1 天，依赖于任务 C
• 任务 F：持续时间 3 天，依赖于任务 D 和任务 E

构建有向图

A (3)
|      \
B (2)  C (4)
|       |
D (2)   E (1)\     /\   /F (3)

计算最早开始时间和最早完成时间

1. 任务 A: ES = 0, EF = 3
2. 任务 B: ES = 3, EF = 5
3. 任务 C: ES = 3, EF = 7
4. 任务 D: ES = 5, EF = 7
5. 任务 E: ES = 7, EF = 8
6. 任务 F: ES = 8, EF = 11

计算最晚开始时间和最晚完成时间

1. 任务 F: LF = 11, LS = 8
2. 任务 D: LF = 8, LS = 6
3. 任务 E: LF = 8, LS = 7
4. 任务 B: LF = 6, LS = 4
5. 任务 C: LF = 7, LS = 3
6. 任务 A: LF = 3, LS = 0

计算总时差和自由时差

1. 任务 A: TF = 0
2. 任务 B: TF = 1
3. 任务 C: TF = 0
4. 任务 D: TF = 1
5. 任务 E: TF = 0
6. 任务 F: TF = 0

找出关键路径

关键路径上的任务总时差为 0，路径为 A -> C -> E -> F。

Java 实现

import java.util.*;public class CriticalPathMethod {static class Task {String id;int duration;List<String> dependencies;Task(String id, int duration, List<String> dependencies) {this.id = id;this.duration = duration;this.dependencies = dependencies;}}static class Graph {Map<String, Task> tasks;Map<String, List<String>> adjList;Map<String, Integer> earliestStart;Map<String, Integer> earliestFinish;Map<String, Integer> latestStart;Map<String, Integer> latestFinish;Map<String, Integer> totalFloat;Map<String, Integer> freeFloat;Graph(List<Task> taskList) {tasks = new HashMap<>();adjList = new HashMap<>();earliestStart = new HashMap<>();earliestFinish = new HashMap<>();latestStart = new HashMap<>();latestFinish = new HashMap<>();totalFloat = new HashMap<>();freeFloat = new HashMap<>();for (Task task : taskList) {tasks.put(task.id, task);adjList.put(task.id, new ArrayList<>());earliestStart.put(task.id, 0);earliestFinish.put(task.id, 0);latestStart.put(task.id, Integer.MAX_VALUE);latestFinish.put(task.id, Integer.MAX_VALUE);totalFloat.put(task.id, 0);freeFloat.put(task.id, 0);}}void addEdge(String from, String to) {adjList.get(from).add(to);}void calculateEarliestTimes() {for (String task : tasks.keySet()) {calculateEarliestTimes(task);}}int calculateEarliestTimes(String task) {if (earliestFinish.get(task) > 0) {return earliestFinish.get(task);}int duration = tasks.get(task).duration;int es = 0;for (String dep : tasks.get(task).dependencies) {es = Math.max(es, calculateEarliestTimes(dep));}earliestStart.put(task, es);earliestFinish.put(task, es + duration);return earliestFinish.get(task);}void calculateLatestTimes() {int maxTime = Collections.max(earliestFinish.values());for (String task : tasks.keySet()) {latestFinish.put(task, maxTime);}for (String task : tasks.keySet()) {calculateLatestTimes(task);}}int calculateLatestTimes(String task) {int duration = tasks.get(task).duration;int lf = latestFinish.get(task);for (String neighbor : adjList.get(task)) {lf = Math.min(lf, calculateLatestTimes(neighbor) - duration);}latestStart.put(task, lf - duration);latestFinish.put(task, lf);return latestStart.get(task);}void calculateTotalAndFreeFloat() {for (String task : tasks.keySet()) {totalFloat.put(task, latestStart.get(task) - earliestStart.get(task));int minFreeFloat = Integer.MAX_VALUE;for (String neighbor : adjList.get(task)) {minFreeFloat = Math.min(minFreeFloat, earliestStart.get(neighbor) - earliestFinish.get(task));}freeFloat.put(task, minFreeFloat == Integer.MAX_VALUE ? totalFloat.get(task) : minFreeFloat);}}List<String> getCriticalPath() {List<String> criticalPath = new ArrayList<>();for (String task : tasks.keySet()) {if (totalFloat.get(task) == 0) {criticalPath.add(task);}}return criticalPath;}}public static void main(String[] args) {List<Task> tasks = Arrays.asList(new Task("A", 3, Collections.emptyList()),new Task("B", 2, Arrays.asList("A")),new Task("C", 4, Arrays.asList("A")),new Task("D", 2, Arrays.asList("B")),new Task("E", 1, Arrays.asList("C")),new Task("F", 3, Arrays.asList("D", "E")));Graph graph = new Graph(tasks);graph.addEdge("A", "B");graph.addEdge("A", "C");graph.addEdge("B", "D");graph.addEdge("C", "E");graph.addEdge("D", "F");graph.addEdge("E", "F");graph.calculateEarliestTimes();graph.calculateLatestTimes();graph.calculateTotalAndFreeFloat();System.out.println("Earliest Start Times: " + graph.earliestStart);System.out.println("Earliest Finish Times: " + graph.earliestFinish);System.out.println("Latest Start Times: " + graph.latestStart);System.out.println("Latest Finish Times: " + graph.latestFinish);System.out.println("Total Float: " + graph.totalFloat);System.out.println("Free Float: " + graph.freeFloat);System.out.println("Critical Path: " + graph.getCriticalPath());}
}