前言
Live beautifully, dream passionately, love completely.
Name：Willam
Time：2017/3/7

1、AOE-網(wǎng)介紹

我們在學習拓撲排序（如果沒學，可以看看這篇博客：拓撲排序詳解）的時候，已經(jīng)接觸了什么是AOV-網(wǎng)，AOV-網(wǎng)是優(yōu)先考慮頂點的思路，而我們也同樣可以優(yōu)先考慮邊，這個就是AOE-網(wǎng)的思路。

若在帶權的有向無環(huán)圖中，以頂點表示事件，以有向邊表示活動，邊上的權值表示活動的開銷（如該活動持續(xù)的時間），則此帶權的有向無環(huán)圖稱為AOE網(wǎng)。記住AOE-網(wǎng)只是比AOV-網(wǎng)多了一個邊的權重，而且AOV-網(wǎng)一般是設計一個龐大的工程各個子工程實施的先后順序，而我們的AOE-網(wǎng)就是不僅僅關系整個工程中各個子工程的實施的先后順序，同時也關系整個工程完成最短時間。

因此，通常在AOE網(wǎng)中列出完成預定工程計劃所需要進行的活動，每個活動計劃完成的時間，要發(fā)生哪些事件以及這些事件與活動之間的關系，從而可以確定該項工程是否可行，估算工程完成的時間以及確定哪些活動是影響工程進度的關鍵。

AOE-網(wǎng)還有一個特點就是：只有一個起點（入度為0的頂點）和一個終點（出度為0的頂點），并且AOE-網(wǎng)有兩個待研究的問題：

1. 完成整個工程需要的時間

2. 哪些活動是影響工程進度的關鍵

2、名詞解釋

• 關鍵路徑：AOE-網(wǎng)中，從起點到終點最長的路徑的長度（長度指的是路徑上邊的權重和）

• 關鍵活動：關鍵路徑上的邊

假設起點是vo，則我們稱從v0到vi的最長路徑的長度為vi的最早發(fā)生時間，同時，vi的最早發(fā)生時間也是所有以vi為尾的弧所表示的活動的最早開始時間，使用e（i）表示活動ai最早發(fā)生時間，除此之外，我們還定義了一個活動最遲發(fā)生時間，使用l（i）表示，不推遲工期的最晚開工時間。我們把e（i）=l（i）的活動ai稱為關鍵活動，因此，這個條件就是我們求一個AOE-網(wǎng)的關鍵路徑的關鍵所在了。

所以，我們現(xiàn)在要求的就是每弧所對應的e（i）和l（i），求這兩個變量的公式是：

變量的介紹：

首先我們假設活動a（i）是弧<j,k>上的活動，j為弧尾頂點，k為弧頭（有箭頭的一邊），ve（j）代表的是弧尾j的最早發(fā)生時間，vl（k）代表的是弧頭k的最遲發(fā)生時間dut（<j,k>）代表該活動要持續(xù)的時間，既是弧的權值

好了，先在我們知道了求e（i）和l（i）就必須先知道各個頂點的ve和vl了，所以下面我們就來求每個頂點ve和vl。其中，我們要知道ve和vl是要分開來求的。

先求ve，從ve（0）=0開始往前推（其實就是從起點開始往后，求各個頂點最早發(fā)生時間），公式如下：

下面我們繼續(xù)求：各個頂點的vl，vl是從vl（n-1）=ve（n-1）往后推進（其實就是從終點開始往前求各個頂點的最遲發(fā)生時間，其中終點的ve和vl是相等的）

vl（i）=Min{vl(j)-dut(<i,j>)}<i,j>屬于S，i=n-2,n-3.....0其中，S是所有以第i個頂點為尾的弧的集合

3、求關鍵路徑的步驟

1. 輸入頂點數(shù)和邊數(shù)，已經(jīng)各個弧的信息建立圖

2. 從源點v1出發(fā)，令ve[0]=0;按照拓撲序列往前求各個頂點的ve。如果得到的拓撲序列個數(shù)小于網(wǎng)的頂點數(shù)n，說明我們建立的圖有環(huán)，無關鍵路徑，直接結束程序

3. 從終點vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓撲序列，往后求其他頂點vl值

4. 根據(jù)各個頂點的ve和vl求每個弧的e（i）和l（i），如果滿足e（i）=l（i），說明是關鍵活動。

4、求關鍵路徑的代碼實現(xiàn)

• CriticalPath.h文件的代碼：

• CriticalPath.cpp文件的代碼

#include'CriticalPath.h'Graph_DG::Graph_DG(int vexnum, int edge) {          /*        初始化一些基本的信息，        包括邊和頂點個數(shù)，各個頂點入度數(shù)組，鄰接表的等        */        this->vexnum = vexnum;        this->edge = edge;        this->arc = new Vnode[this->vexnum];        this->indegree = new int[this->vexnum];        this->ve = new int[this->vexnum];        this->vl = new int[this->vexnum];        for (int i = 0; i < this->vexnum; i++) {            this->indegree[i] = 0;            this->ve[i] = 0;            this->arc[i].firstarc = NULL;            this->arc[i].data = 'v' + to_string(i + 1);        }}//釋放內存空間Graph_DG::~Graph_DG() {    ArcNode * p, *q;    for (int i = 0; i < this->vexnum; i++) {        if (this->arc[i].firstarc) {            p = this->arc[i].firstarc;            while (p) {                q = p->next;                delete p;                p = q;            }        }    }    delete[] this->arc;    delete[] this->indegree;}//判斷我們每次輸入的的邊的信息是否合法//頂點從1開始編號bool Graph_DG::check_edge_value(int start, int end,int weight) {    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {        return false;    }    return true;}void Graph_DG::createGraph() {    cout << '請輸入每條邊的起點和終點的編號（頂點從1開始編號）以及每條邊的權重' << endl;    int count = 0; //記錄初始化邊的條數(shù)    int start, end, weight;    while (count != this->edge) {        cin >> start >> end >> weight;        while (!check_edge_value(start, end, weight)) {            cout << '輸入的信息不合法，請重新輸入：' << endl;            cin >> start >> end >> weight;        }        ArcNode * temp = new ArcNode;        temp->start = start-1;        temp->end = end-1;        temp->weight = weight;        temp->next = NULL;        //如果當前頂點的還沒有邊依附時，        ++indegree[temp->end];   //對應的弧頭的頂點的入度加1        if (this->arc[start - 1].firstarc == NULL) {            this->arc[start - 1].firstarc = temp;        }        else {            ArcNode * now = this->arc[start - 1].firstarc;            while (now->next) {                now = now->next;            }//找到該鏈表的最后一個結點            now->next = temp;        }        ++count;    }}void Graph_DG::print() {    cout << '圖的鄰接表為：' << endl;    int  count = 0;    while (count != this->vexnum) {        cout << this->arc[count].data << ' ';        ArcNode * temp = this->arc[count].firstarc;        while (temp) {            cout << '<'                << this->arc[temp->start].data                << ','                << this->arc[temp->end].data                << '>='                << temp->weight                << ' ';            temp = temp->next;        }        cout << '^' << endl;        ++count;    }}bool Graph_DG::topological_sort() {    cout << '圖的拓撲序列為：' << endl;    stack<int> s; //保存入度為0的頂點下標    ArcNode * temp;    int i;    for (i = 0; i < this->vexnum; i++) {        if (!indegree[i]) s.push(i); //入度為0 ，則入棧    }    //count用于計算輸出的頂點個數(shù)    int count = 0;    while (!s.empty()) {//如果棧為空，退出循環(huán)        i = s.top(); //i等于棧頂?shù)脑?       s.pop();        cout << this->arc[i].data << ' ';//輸出拓撲序列        temp = this->arc[i].firstarc;        this->List.push(i);        while (temp) {            if (!(--indegree[temp->end])) {//如果入度減少到為0，則入棧                s.push(temp->end);            }            //同時更新ve的值            if ((ve[i] + temp->weight) > ve[temp->end]) {                ve[temp->end] = ve[i] + temp->weight;            }            temp = temp->next;        }        ++count;    }    if (count == this->vexnum) {        cout << endl;        return true;    }    cout << '此圖有環(huán)，無拓撲序列' << endl;    return false;//說明這個圖有環(huán)}bool Graph_DG::CriticalPath() {    if (!this->topological_sort()) {        cout << '此圖有環(huán)，無關鍵路徑' << endl;        return false;    }    cout << '圖的關鍵路徑為：' << endl;    //初始化vl的值都為ve[this->vexnum-1]    int k;    for (k = 0; k < this->vexnum; k++) {        vl[k] = ve[this->vexnum - 1];    }    ArcNode * temp;    while (!this->List.empty()) {        k = List.top();//從逆拓撲排序開始，求vl        List.pop();        temp = this->arc[k].firstarc;        while (temp) {            //dut<k,temp->end>，從以第k個頂點為弧尾集合中選擇一個最小的值            //來作為第i個頂點的最遲發(fā)生時間            if (vl[k] > (vl[temp->end] - temp->weight)) {                vl[k] = vl[temp->end] - temp->weight;            }            temp = temp->next;        }    }    int ee;    int el;    for (k = 0; k < this->vexnum; k++) {        temp= temp = this->arc[k].firstarc;        while (temp) {            ee = ve[k];            el = vl[temp->end] - temp->weight;            if (ee == el) {//這兩個值相等，說明它為關鍵活動：                cout << this->arc[k].data                    << '----'                    << this->arc[temp->end].data                    << '='                    << temp->weight                    << endl;            }            temp = temp->next;        }    }}

• main.cpp文件的代碼

構造下圖：

輸入：

9 111 2 61 3 41 4 52 5 13 5 14 6 25 7 95 8 76 8 47 9 28 9 4

輸出：

從輸出可以看出，這個圖有兩條關鍵路徑：
第一條就是：

第二條是：

v1--v2--v5--v8--v9

我們在構造下圖的關鍵路徑：

輸入：

輸出：

從輸出可以看出，這個圖有一條關鍵路徑：

v1--v3--v4--v6