相關(guān)概念

AOE網(wǎng)：在一個表示工程的帶權(quán)有向圖中醉拓，用頂點表示事件，用有向邊表示活動粥航，用邊上的權(quán)值表示活動的持續(xù)時間粟焊，這種有向圖的邊表示活動的網(wǎng)冤狡，我們稱之為AOE網(wǎng)(Activity On Edge Network)。

關(guān)鍵路徑與拓?fù)渑判虻膮^(qū)別：拓?fù)渑判蛑饕墙鉀Q一個工程能否順利進(jìn)行的問題项棠，關(guān)鍵路徑解決的是工程完成所需要的最短時間問題悲雳。換句話說，關(guān)鍵路徑問題需要在拓?fù)渑判虻幕A(chǔ)上得到完成工程的最短時間香追，因為工程首先必須是可以被完成的合瓢，也就是網(wǎng)中不存在環(huán)路時，才能進(jìn)一步討論工程完成所需的最短時間問題透典。

AOE網(wǎng)和AOV網(wǎng)：AOV網(wǎng)是頂點表示活動的網(wǎng)晴楔，它只描述活動之間的制約關(guān)系；AOE網(wǎng)是用邊表示活動的網(wǎng)峭咒，邊上的權(quán)值表示活動持續(xù)的時間税弃。

關(guān)鍵路徑：從源點到匯點具有最大長度的路徑稱為關(guān)鍵路徑，在關(guān)鍵路徑上的活動叫關(guān)鍵活動讹语。只有縮短關(guān)鍵路徑上的關(guān)鍵活動時間才可以減少整個工期長度钙皮。

關(guān)鍵路徑算法參數(shù)介紹

事件的最早發(fā)生時間etv(earliest time of vertex):頂點Vn的最早發(fā)生時間;

事件的最晚發(fā)生時間ltv(latest tiem of vertex):頂點Vn的最晚發(fā)生時間;

活動的最早開工時間ete(earliest time of edge):弧En的最早發(fā)生時間;

活動的最晚開工時間lte(latest time of edge):弧En的最晚發(fā)生時間蜂科，也就是不推遲工期的最晚開工時間顽决。

關(guān)鍵路徑算法由etv和ltv求得ete和lte,當(dāng)ete與lte相等時表示活動沒有空閑時間短条，是關(guān)鍵活動。

etv和ltv數(shù)組的計算方法

etv數(shù)組計算公式.png

P[k]表示所有到達(dá)頂點Vk的弧的集合才菠，即Vk是弧的終點茸时。

ltv數(shù)組計算公式.png

S[k]表示所有從頂點Vk出發(fā)的弧的集合，即Vk是弧的起點赋访。

源代碼

帶權(quán)有向圖采用鄰接表的數(shù)據(jù)結(jié)構(gòu)表示

頂點表結(jié)點類

/**
 * 頂點表結(jié)點類
 * 
 * @author Shaw
 *
 */
class VertexNode {
    // 頂點入度
    private int in;
    // 頂點域
    private String data;
    // 指向邊表
    private EdgeNode firstEdge;

    public VertexNode(int in, String data, EdgeNode firstEdge) {
        super();
        this.in = in;
        this.data = data;
        this.firstEdge = firstEdge;
    }

    public int getIn() {
        return in;
    }

    public void setIn(int in) {
        this.in = in;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public EdgeNode getFirstEdge() {
        return firstEdge;
    }

    public void setFirstEdge(EdgeNode firstEdge) {
        this.firstEdge = firstEdge;
    }
}

邊表頂點類

/**
 * 邊表頂點類
 * @author Shaw
 *
 */
class EdgeNode {
    //鄰接點域可都，存儲該頂點對應(yīng)的下標(biāo)
    private int adjvex;
    //權(quán)值域
    private int weight;
    //指向下一個鄰接點
    private EdgeNode next;
    
    
    public EdgeNode(int adjvex, int weight, EdgeNode next) {
        super();
        this.adjvex = adjvex;
        this.weight = weight;
        this.next = next;
    }


    public int getAdjvex() {
        return adjvex;
    }


    public void setAdjvex(int adjvex) {
        this.adjvex = adjvex;
    }


    public int getWeight() {
        return weight;
    }


    public void setWeight(int weight) {
        this.weight = weight;
    }


    public EdgeNode getNext() {
        return next;
    }


    public void setNext(EdgeNode next) {
        this.next = next;
    }
}

關(guān)鍵路徑算法核心類

/**
 * 關(guān)鍵路徑算法
 * 
 * @author Shaw
 *
 */
class CriticalPath {
    private List<VertexNode> verList;
    private int[] etv; // (earliest time of edge)事件最早發(fā)生時間數(shù)組
    private int[] ltv; // (latest time of edge)事件最遲發(fā)生時間數(shù)組
    private Stack<Integer> stack2; // 用于存放拓?fù)渑判蚪Y(jié)果的棧

    // 建圖
    public void buildAoeGraph() {
        VertexNode v0 = new VertexNode(0, "v0", null);
        EdgeNode v0e1 = new EdgeNode(2, 4, null);
        EdgeNode v0e2 = new EdgeNode(1, 3, null);
        v0.setFirstEdge(v0e1);
        v0e1.setNext(v0e2);

        VertexNode v1 = new VertexNode(0, "v1", null);
        EdgeNode v1e1 = new EdgeNode(4, 6, null);
        EdgeNode v1e2 = new EdgeNode(3, 5, null);
        v1.setFirstEdge(v1e1);
        v1e1.setNext(v1e2);

        VertexNode v2 = new VertexNode(0, "v2", null);
        EdgeNode v2e1 = new EdgeNode(5, 7, null);
        EdgeNode v2e2 = new EdgeNode(3, 8, null);
        v2.setFirstEdge(v2e1);
        v2e1.setNext(v2e2);

        VertexNode v3 = new VertexNode(0, "v3", null);
        EdgeNode v3e1 = new EdgeNode(4, 3, null);
        v3.setFirstEdge(v3e1);

        VertexNode v4 = new VertexNode(0, "v4", null);
        EdgeNode v4e1 = new EdgeNode(7, 4, null);
        EdgeNode v4e2 = new EdgeNode(6, 9, null);
        v4.setFirstEdge(v4e1);
        v4e1.setNext(v4e2);

        VertexNode v5 = new VertexNode(0, "v5", null);
        EdgeNode v5e1 = new EdgeNode(7, 6, null);
        v5.setFirstEdge(v5e1);

        VertexNode v6 = new VertexNode(0, "v6", null);
        EdgeNode v6e1 = new EdgeNode(9, 2, null);
        v6.setFirstEdge(v6e1);

        VertexNode v7 = new VertexNode(0, "v7", null);
        EdgeNode v7e1 = new EdgeNode(8, 5, null);
        v7.setFirstEdge(v7e1);

        VertexNode v8 = new VertexNode(0, "v8", null);
        EdgeNode v8e1 = new EdgeNode(9, 3, null);
        v8.setFirstEdge(v8e1);

        VertexNode v9 = new VertexNode(0, "v9", null);

        verList = new ArrayList<>();
        verList.add(v0);
        verList.add(v1);
        verList.add(v2);
        verList.add(v3);
        verList.add(v4);
        verList.add(v5);
        verList.add(v6);
        verList.add(v7);
        verList.add(v8);
        verList.add(v9);
    }

    // 拓?fù)渑判颍糜陉P(guān)鍵路徑的計算
    // 求出事件的最早發(fā)生時間數(shù)組etv[]
    public void topologicalSortForCriticalPath() {
        Stack<Integer> stack = new Stack<>();
        etv = new int[verList.size()];
        stack2 = new Stack<>();
        int count = 0;
        // 初始化所有頂點表結(jié)點的入度值
        for (int i = 0; i < verList.size(); i++) {
            // 初始化etv數(shù)組
            etv[i] = 0;
            EdgeNode edgeNode = verList.get(i).getFirstEdge();
            while (edgeNode != null) {
                // 邊集表中出現(xiàn)的下標(biāo)(adjvex)所對應(yīng)的頂點入度加1
                VertexNode vertexNode = verList.get(edgeNode.getAdjvex());
                vertexNode.setIn(vertexNode.getIn() + 1);
                edgeNode = edgeNode.getNext();
            }
        }
        // 將所有入度為0的頂點入棧
        for (int i = 0; i < verList.size(); i++) {
            if (verList.get(i).getIn() == 0) {
                stack.push(i);
            }
        }

        while (!stack.isEmpty()) {
            // 從棧中彈出一個入度為0的頂點
            int vertex = stack.pop();
            // 將出棧的頂點壓入stack2棧中用于關(guān)鍵路徑算法
            stack2.push(vertex);
            count++;
            // 獲取彈出的頂點指向的第一個邊結(jié)點
            EdgeNode edgeNode = verList.get(vertex).getFirstEdge();
            while (edgeNode != null) {
                // 獲取邊表結(jié)點的Adjvex值蚓耽，該值存儲對應(yīng)頂點表結(jié)點的下標(biāo)值
                int adjvex = edgeNode.getAdjvex();
                // 獲取邊表結(jié)點指向的頂點表結(jié)點
                VertexNode vertexNode = verList.get(adjvex);
                // 刪除邊結(jié)點渠牲，也就是將對應(yīng)的頂點表結(jié)點的入度減1
                vertexNode.setIn(vertexNode.getIn() - 1);
                // 如果該頂點表結(jié)點入度為0時壓棧
                if (vertexNode.getIn() == 0) {
                    stack.push(adjvex);
                }
                // 求各頂點事件的最早發(fā)生時間值
                if ((etv[vertex] + edgeNode.getWeight()) > etv[adjvex]) {
                    etv[adjvex] = etv[vertex] + edgeNode.getWeight();
                }
                // 獲取下一個邊表結(jié)點的值
                edgeNode = edgeNode.getNext();
            }
        }
    }

    // 關(guān)鍵路徑算法
    public void CriticalPath() {
        EdgeNode edgeNode;
        int i, stacktop, k, j;
        // 活動最早發(fā)生時間和最遲發(fā)生時間
        int ete, lte;
        topologicalSortForCriticalPath();
        System.out.println("etv數(shù)組：");
        for (i = 0; i < verList.size(); i++) {
            System.out.print(etv[i] + " ");
        }
        // 事件最晚發(fā)生時間
        ltv = new int[verList.size()];
        // 初始化ltv數(shù)組
        for (i = 0; i < verList.size(); i++) {
            ltv[i] = etv[verList.size() - 1];
        }
        // while循環(huán)計算具體的ltv數(shù)組的值
        while (!stack2.isEmpty()) {
            //從拓?fù)渑判虻慕Y(jié)果從后往前遍歷，因為先是從棧1中彈出后在壓入棧2的步悠，所以棧2的頂是拓?fù)渑判虻淖詈笠粋€結(jié)果
            stacktop = stack2.pop();
            edgeNode = verList.get(stacktop).getFirstEdge();
            while (edgeNode != null) {
                k = edgeNode.getAdjvex();
                if (ltv[k] - edgeNode.getWeight() < ltv[stacktop]) {
                    ltv[stacktop] = ltv[k] - edgeNode.getWeight();
                }
                edgeNode = edgeNode.getNext();
            }
        }
        System.out.println("\nltv數(shù)組：");
        for (i = 0; i < verList.size(); i++) {
            System.out.print(ltv[i] + " ");
        }
        System.out.println("\n關(guān)鍵路徑：");
            for (j = 0; j < verList.size(); j++) {
                edgeNode = verList.get(j).getFirstEdge();
                while (edgeNode != null) {
                    k = edgeNode.getAdjvex();
                    ete = etv[j];
                    lte = ltv[k] - edgeNode.getWeight();
                     if (ete == lte) {
                     System.out.println("<"+verList.get(j).getData()+","+verList.get(k).getData()+"> weight : "+edgeNode.getWeight());
                     }
                    edgeNode = edgeNode.getNext();
                }
            }
        }
    }

測試圖以及鄰接表

有向帶權(quán)無換圖.png

鄰接表圖.png

測試程序

public class CriticalPathMain {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        CriticalPath criticalPath = new CriticalPath();
        criticalPath.buildAoeGraph();
        criticalPath.CriticalPath();
    }
}

測試結(jié)果

關(guān)鍵路徑算法結(jié)果圖.png