每日算法 — 使用java实现关键路径：AOE网络与工程进度优化

关键路径法（Critical Path Method, CPM）是项目管理和运筹学中的核心算法，用于分析带权有向无环图（DAG）中完成所有任务所需的最短时间，以及识别哪些任务的延期会直接影响整个项目的工期。本文将基于AOE网（Activity On Edge network）模型，用Java实现关键路径的完整计算，包括最早/最晚时间、关键活动和项目缓冲分析。

AOE网模型

AOE网是一种带权有向无环图：
– 顶点（事件）：表示某个或某些活动完成的时刻
– 有向边（活动）：表示任务，权重为任务持续时间
– 源点：入度为0的起点，表示项目开始
– 汇点：出度为0的终点，表示项目结束

关键路径是AOE网中从源点到汇点的最长路径，路径上所有活动的持续时间之和即为项目的最短完成时间。关键路径上的任何活动延期，都将导致整个项目延期。

算法框架

计算关键路径需要四个步骤：

拓扑排序：确定事件的先后依赖顺序
最早时间（ve）：从源点出发，按拓扑序计算每个事件的最早发生时间
最晚时间（vl）：从汇点反向，按逆拓扑序计算每个事件的最晚发生时间
关键活动判定：活动的最早开始时间等于最晚开始时间，即为关键活动

Java实现

import java.util.*;

/**
 * 关键路径法（CPM）实现
 * 基于AOE网计算项目最短工期和关键路径
 */
public class CriticalPathMethod {

    static class Activity {
        int from, to;      // 起点事件和终点事件
        int duration;      // 活动持续时间
        String name;       // 活动名称

        Activity(int from, int to, int duration, String name) {
            this.from = from;
            this.to = to;
            this.duration = duration;
            this.name = name;
        }
    }

    static class Graph {
        int vertices;                  // 顶点（事件）数量
        List<Activity>[] adj;          // 邻接表
        int[] inDegree;                // 入度数组

        @SuppressWarnings("unchecked")
        Graph(int vertices) {
            this.vertices = vertices;
            adj = new ArrayList[vertices];
            for (int i = 0; i < vertices; i++) {
                adj[i] = new ArrayList<>();
            }
            inDegree = new int[vertices];
        }

        void addActivity(int from, int to, int duration, String name) {
            adj[from].add(new Activity(from, to, duration, name));
            inDegree[to]++;
        }
    }

    static class CriticalPathResult {
        int[] ve;                      // 最早发生时间
        int[] vl;                      // 最晚发生时间
        int projectDuration;           // 项目总工期
        List<Activity> criticalActivities; // 关键活动列表
        List<Integer> criticalPath;    // 关键路径（顶点序列）
        Map<String, int[]> activityTimes; // 每个活动的[最早开始, 最晚开始, 缓冲]

        CriticalPathResult(int vertices) {
            ve = new int[vertices];
            vl = new int[vertices];
            criticalActivities = new ArrayList<>();
            criticalPath = new ArrayList<>();
            activityTimes = new HashMap<>();
        }
    }

    /**
     * 拓扑排序（Kahn算法）
     * @return 拓扑序列表，如果存在环返回null
     */
    public static List<Integer> topologicalSort(Graph graph) {
        List<Integer> order = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int[] inDegree = graph.inDegree.clone();

        // 入度为0的顶点入队
        for (int i = 0; i < graph.vertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);

            for (Activity act : graph.adj[u]) {
                inDegree[act.to]--;
                if (inDegree[act.to] == 0) {
                    queue.offer(act.to);
                }
            }
        }

        // 如果排序顶点数不足，说明存在环
        return order.size() == graph.vertices ? order : null;
    }

    /**
     * 计算关键路径
     */
    public static CriticalPathResult computeCriticalPath(Graph graph) {
        CriticalPathResult result = new CriticalPathResult(graph.vertices);

        // 1. 拓扑排序
        List<Integer> topoOrder = topologicalSort(graph);
        if (topoOrder == null) {
            throw new IllegalArgumentException("图中存在环，无法计算关键路径");
        }

        // 2. 计算最早发生时间 ve（从源点正向递推）
        Arrays.fill(result.ve, 0);
        for (int u : topoOrder) {
            for (Activity act : graph.adj[u]) {
                int v = act.to;
                // 事件v的最早时间 = max(所有前驱事件的最早时间 + 活动持续时间)
                result.ve[v] = Math.max(result.ve[v], result.ve[u] + act.duration);
            }
        }

        int sink = topoOrder.get(topoOrder.size() - 1);
        result.projectDuration = result.ve[sink];

        // 3. 计算最晚发生时间 vl（从汇点反向递推）
        Arrays.fill(result.vl, result.projectDuration);
        for (int i = topoOrder.size() - 1; i >= 0; i--) {
            int u = topoOrder.get(i);
            for (Activity act : graph.adj[u]) {
                int v = act.to;
                // 事件u的最晚时间 = min(所有后继事件的最晚时间 - 活动持续时间)
                result.vl[u] = Math.min(result.vl[u], result.vl[v] - act.duration);
            }
        }

        // 4. 判定关键活动
        for (int u = 0; u < graph.vertices; u++) {
            for (Activity act : graph.adj[u]) {
                int v = act.to;
                // 活动的最早开始时间 = 起点事件的最早时间
                int e = result.ve[u];
                // 活动的最晚开始时间 = 终点事件的最晚时间 - 活动持续时间
                int l = result.vl[v] - act.duration;
                // 缓冲时间 = 最晚开始 - 最早开始
                int slack = l - e;

                result.activityTimes.put(act.name, new int[]{e, l, slack});

                // 最早开始等于最晚开始，说明是关键活动
                if (e == l) {
                    result.criticalActivities.add(act);
                }
            }
        }

        // 5. 重构关键路径（顶点序列）
        reconstructCriticalPath(graph, result, topoOrder.get(0), sink);

        return result;
    }

    /**
     * 从源点到汇点重构一条关键路径
     */
    private static void reconstructCriticalPath(Graph graph, CriticalPathResult result, 
                                                int source, int sink) {
        result.criticalPath.add(source);
        int current = source;

        while (current != sink) {
            boolean found = false;
            for (Activity act : graph.adj[current]) {
                int e = result.ve[current];
                int l = result.vl[act.to] - act.duration;
                if (e == l) { // 关键活动
                    result.criticalPath.add(act.to);
                    current = act.to;
                    found = true;
                    break;
                }
            }
            if (!found) break;
        }
    }

    /**
     * 打印结果
     */
    public static void printResult(CriticalPathResult result) {
        System.out.println("=== 关键路径分析结果 ===\n");
        System.out.println("项目最短工期: " + result.projectDuration + " 天\n");

        System.out.println("事件时间表:");
        System.out.println("事件\t最早时间(ve)\t最晚时间(vl)\t缓冲");
        for (int i = 0; i < result.ve.length; i++) {
            int slack = result.vl[i] - result.ve[i];
            System.out.printf("%d\t%d\t\t%d\t\t%d%n", i, result.ve[i], result.vl[i], slack);
        }

        System.out.println("\n活动分析:");
        System.out.println("活动\t最早开始\t最晚开始\t缓冲\t关键?");
        for (Map.Entry<String, int[]> entry : result.activityTimes.entrySet()) {
            int[] times = entry.getValue();
            boolean isCritical = (times[0] == times[1]);
            System.out.printf("%s\t%d\t\t%d\t\t%d\t%s%n",
                entry.getKey(), times[0], times[1], times[2], 
                isCritical ? "是" : "否");
        }

        System.out.println("\n关键活动:");
        for (Activity act : result.criticalActivities) {
            System.out.printf("  %s: %d → %d (持续%d天)%n", 
                act.name, act.from, act.to, act.duration);
        }

        System.out.println("\n关键路径（事件序列）:");
        for (int i = 0; i < result.criticalPath.size(); i++) {
            System.out.print(result.criticalPath.get(i));
            if (i < result.criticalPath.size() - 1) System.out.print(" → ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 构建示例AOE网
        // 事件: 0(开始) → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8(结束)
        Graph graph = new Graph(9);

        // 活动: (起点, 终点, 持续时间, 名称)
        graph.addActivity(0, 1, 6, "a1");
        graph.addActivity(0, 2, 4, "a2");
        graph.addActivity(0, 3, 5, "a3");
        graph.addActivity(1, 4, 1, "a4");
        graph.addActivity(2, 4, 1, "a5");
        graph.addActivity(3, 5, 2, "a6");
        graph.addActivity(4, 6, 9, "a7");
        graph.addActivity(4, 7, 7, "a8");
        graph.addActivity(5, 7, 4, "a9");
        graph.addActivity(6, 8, 2, "a10");
        graph.addActivity(7, 8, 4, "a11");

        System.out.println("=== 关键路径法（CPM）演示 ===\n");

        CriticalPathResult result = computeCriticalPath(graph);
        printResult(result);

        // 项目缓冲分析
        System.out.println("\n=== 项目优化建议 ===");
        for (Map.Entry<String, int[]> entry : result.activityTimes.entrySet()) {
            int[] times = entry.getValue();
            if (times[2] > 0) {
                System.out.printf("活动 %s 有 %d 天缓冲，可适当调配资源%n", 
                    entry.getKey(), times[2]);
            }
        }
    }
}

最早时间与最晚时间的递推公式

最早发生时间 ve[j]：

ve[j] = max{ve[i] + weight(i,j)}  对所有<i,j>∈E
ve[源点] = 0

含义：事件j必须在所有前驱活动都完成后才能发生，所以取所有前驱路径中的最大值。

最晚发生时间 vl[i]：

vl[i] = min{vl[j] - weight(i,j)}  对所有<i,j>∈E
vl[汇点] = ve[汇点]

含义：事件i的最晚发生时间不能影响任何后继事件的最晚时间，所以取所有后继路径中的最小值。

关键活动判定条件：

e(i,j) = ve[i]          // 活动<i,j>的最早开始时间
l(i,j) = vl[j] - weight(i,j)  // 活动<i,j>的最晚开始时间

若 e(i,j) == l(i,j)，则活动<i,j>为关键活动

与PERT的区别

CPM（关键路径法）和PERT（计划评审技术）都用于项目管理，但有以下区别：

特性	CPM	PERT
活动时间	确定性（单一估计值）	概率性（乐观/最可能/悲观估计）
适用场景	重复性项目（建筑工程）	研发项目（软件开发）
核心输出	关键路径、缓冲时间	期望工期、完成概率
优化重点	资源平衡、工期压缩	风险评估、进度控制

实际应用场景

建筑工程：施工流程中各工序的先后依赖和工期优化
软件开发：里程碑规划、依赖模块的交付时间协调
生产制造：流水线工序调度、瓶颈识别
事件筹划：大型活动的筹备流程优化
网络数据传输：数据包在多跳网络中的传输时延分析

复杂度分析

拓扑排序：O(V + E)
最早/最晚时间计算：O(V + E)，每条边被访问一次
关键活动判定：O(E)
总时间复杂度：O(V + E)
空间复杂度：O(V + E)

算法优化方向

多源多汇处理：添加虚拟源点和虚拟汇点统一处理
资源约束调度：在关键路径基础上考虑资源有限性（RCPSP问题）
工期压缩：计算压缩单位工期所需的最小成本（时间-成本权衡）
随机工期：结合PERT的三点估计，用蒙特卡洛模拟评估完成概率

常见问题

环检测：AOE网必须是有向无环图，否则关键路径无意义。拓扑排序可检测环。
多条关键路径：一个项目可能有多条关键路径，所有路径上的活动都需要重点关注。
浮动时间：非关键活动的总浮动时间（Total Float）和自由浮动时间（Free Float）需要区分。
动态更新：项目执行过程中，实际进度与计划偏差时，需要重新计算关键路径。

总结

关键路径法将复杂的项目管理问题转化为图论中的最长路径问题，通过拓扑排序和动态规划高效求解。掌握CPM不仅意味着能计算项目工期，更重要的是理解”瓶颈决定产出”的系统思维——关键路径上的任何延误都会传导到整个项目，而非关键路径的缓冲则提供了资源调配的灵活性。这种思维方式在软件工程、生产管理乃至个人时间管理中都有广泛应用。

Tagged with: AOE网 CPM 关键活动关键路径工程优化拓扑排序项目管理