关键路径

AOE网

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称之为AOE网。

路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
关键路径是：从源点到终点的最大路径长度
顶点代表事件
ve:事件最早开始时间
vl:事件最晚开始时间
边表示活动
e:活动最早开始时间
l:活动最晚开始时间
ve=e
l=vl-dust(活动持续时间==权值)
e=l的活动为关键路径活动

    private static class CriticalEdgeNode {

        //邻接点域，存储该顶点对应的下标
        private int adjvex;

        //权值
        private int weight;

        //下一领节点
        private CriticalEdgeNode criticalEdgeNode;

        public CriticalEdgeNode(int adjvex) {
            this.adjvex = adjvex;
        }

        public CriticalEdgeNode(int adjvex, int weight) {
            this.adjvex = adjvex;
            this.weight = weight;
        }

        public CriticalEdgeNode(int adjvex, int weight,
                                CriticalEdgeNode criticalEdgeNode) {
            this.adjvex = adjvex;
            this.weight = weight;
            this.criticalEdgeNode = criticalEdgeNode;
        }
    }

    private static class CriticalVertexNode {
        //顶点入度
        private int in;

        //顶点信息
        private Object data;

        //边信息
        private CriticalEdgeNode firstedge;

        public CriticalVertexNode(int in, Object data) {
            this.in = in;
            this.data = data;
        }

        public CriticalVertexNode(Object data) {
            this.data = data;
        }

        public CriticalVertexNode(int in, Object data, CriticalEdgeNode firstedge) {
            this.in = in;
            this.data = data;
            this.firstedge = firstedge;
        }
    }

    private Stack<Integer> topologicalSortStack = new Stack<>();

    //时间最晚开始时间
    private int[] ve;

    /**
     * 使用邻接矩阵来进行拓扑排序算法
     *
     * 将入度为0的顶点入栈
     *
     * 栈不空，则弹出，再将相连的顶点入度减一
     *
     * @param vertexNodes
     */
    public void topologicalSort(CriticalVertexNode[] vertexNodes) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < vertexNodes.length; i++) {
            if (vertexNodes[i].in == 0) {
                stack.push(i);
            }
        }

        ve = new int[vertexNodes.length];
        //记录出栈个数
        int count = 0;
        while (!stack.isEmpty()) {

            int index = stack.pop();

            //拓扑序列
            topologicalSortStack.push(index);

            count++;

            System.out.print(vertexNodes[index].data + "     ");

            for (CriticalEdgeNode x = vertexNodes[index].firstedge; x != null; x = x.criticalEdgeNode) {
                if (--vertexNodes[x.adjvex].in == 0) {
                    stack.push(x.adjvex);
                }

                //获取最早开始时间，下个顶点的最早开始时间 + 权值，为上个顶点的最早开始时间。
                if (ve[index] + x.weight > ve[x.adjvex]) {
                    ve[x.adjvex] = ve[index] + x.weight;
                }

            }

        }

        if (count < vertexNodes.length) {
            throw new RuntimeException("图存在回路");
        }
    }

    /**
     * 关键路径算法
     *
     * 求实活动最早开始时间、最晚开始时间
     * 相等的话就是关键路径
     *
     * @param vertexNodes
     */
    public void critical(CriticalVertexNode[] vertexNodes) {

        topologicalSort(vertexNodes);

        //事件最早开始时间,初始化
        int[] vl = new int[vertexNodes.length];
        for (int i = 0; i < vertexNodes.length; i++) {
            vl[i] = ve[vertexNodes.length - 1];
        }

        while (!topologicalSortStack.isEmpty()) {
            int index = topologicalSortStack.pop();
            for (CriticalEdgeNode x = vertexNodes[index].firstedge; x != null; x = x.criticalEdgeNode) {

                //当前节点的最晚时间，为下一节点的最晚时间-当前权值
                if (vl[x.adjvex] - x.weight < vl[index]) {
                    vl[index] = vl[x.adjvex] - x.weight;
                }
            }

        }

        //活动最晚开始时间
        int l;

        //活动最早开始时间
        int e;

        System.out.println("关键路径：");
        //求活动最早最晚开始时间 最早开始时间=事件最早开始时间，最晚开始时间=时间最晚开始时间-权值
        for (int i = 0; i < vertexNodes.length; i++) {
            for (CriticalEdgeNode x = vertexNodes[i].firstedge; x != null; x = x.criticalEdgeNode) {
                e = ve[i];
                l = vl[x.adjvex] - x.weight;

                if(e == l){
                    System.out.print("   " + vertexNodes[i].data);
                }

            }
        }

    }