介紹

• 在AOV網(wǎng)的基礎(chǔ)上，如果用對應(yīng)邊來表示活動持續(xù)時間，這種有向圖被稱為AOE網(wǎng)
• 在AOE網(wǎng)中，入度為0的為源點，出度為0的為匯點，整張網(wǎng)看做是一件事情完成的過程，那么這兩個點就是事情的開始和結(jié)束。每個活動持續(xù)的時間之和稱為路徑長度，從源點到匯點具有的最大長度的路徑就成稱為關(guān)鍵路徑，關(guān)鍵路徑上的活動稱為關(guān)鍵活動。

關(guān)鍵路徑用來計算整個活動總耗時最短的情況。假如有這樣一張AOE網(wǎng)，在完成從1到3的過程中，每件事情需要的時間為邊上的權(quán)值，那么從開頭到結(jié)束，由于完成4時2,3也可以同時完成，那么需要的最短時間就是4+1=5

那么，1-4-3就是一條關(guān)鍵路徑

不難發(fā)現(xiàn)，這條路徑是把空余時間“塞滿”的路徑。假設(shè)有一件事持續(xù)時間為1h,在12點-15點都可以做，那么這件事的最早開始時間為12點，最晚開始時間為14點，這中間還有兩個小時的空隙，時間沒有“塞滿”，那么就不會構(gòu)成關(guān)鍵路徑

所以，判斷關(guān)鍵事件的標準就是其最早開始時間與最晚開始時間是否相等

如何求關(guān)鍵路徑

1. 繪制計劃圖，標注其持續(xù)時間
2. 根據(jù)各活動的依賴關(guān)系，計算其最早開始時間和最晚開始時間
3. 計算每個活動的最早完成時間和最晚完成時間（由2結(jié)果可以推導出）
4. 找到最早開始時間與最晚開始時間相等的事件，這些活動構(gòu)成了關(guān)鍵路徑

具體實現(xiàn)

由于計算關(guān)鍵路徑之前需要先理清事件的先后關(guān)系，所以在找關(guān)鍵路徑之前需要先對網(wǎng)圖進行拓撲排序，不同的是，我們需要在鄰接表中加入代表邊權(quán)值的值域。

typedef struct edge{int adjvex;//鄰接點域，用于儲存該頂點對應(yīng)下標int info;//儲存權(quán)值int weight;//儲存邊的權(quán)值struct edge* next;//鏈域，指向下一個鄰接點
}edge;
typedef struct vex{int v;//儲存頂點int in;//記錄入度；edge* first;//邊表頭指針
}vex,adjlist[MAX];
//儲存鄰接鏈表構(gòu)成的網(wǎng)圖信息
typedef struct{adjlist al;int numE,numN;
}graphAL;

拓撲排序過程中也需要加入對時間的判斷處理，并額外記錄拓撲排序的結(jié)果

int et[MAX],lt[MAX];//記錄最早時間和最晚時間
bool topo(graphAL g){int n=0;//記錄輸出的頂點值，判斷是否為AOV網(wǎng)deque <int>q;//創(chuàng)建隊列for (int i=0;i<g.numN;i++){if (g.al[i].in==0){//入度為0q.push_back(i);//入隊}}deque <int>q2;//用于儲存拓撲序列for (int i=0;i<g.numN;i++){et[i]=0;//初始化}while(!q.empty()){cout<<q.front()<<" ";//將入度為0的頂點輸出n++;//輸出的頂點數(shù)加1edge* e=g.al[q.front()].first;q2.push_front(q.front());//記錄彈出的頂點int top=q.front();q.pop_front();//此頂點出隊while(e){//處理其相鄰頂點int temp=e->adjvex;//記錄相鄰頂點if (g.al[temp].in==1)//入度為1，說明去掉與原頂點相連的邊后入度為0q.push_back(temp);e=e->next;//繼續(xù)處理下一個相鄰頂點if (et[top]+e->weight>et[temp]) et[temp]=et[top]+e->weight;}}if (n!=g.numN) return false;else return true;
}

關(guān)鍵路徑的求取（隊列2與最早發(fā)生時間數(shù)組需要定義在全局或者傳入函數(shù)中）

void CriticaPath(graphAL g){int e,l;//最早和最晚發(fā)生時間topo(g);//首先進行拓撲排序int ltv[g.numN];//最晚發(fā)生時間數(shù)組for (int i=0;i<g.numN;i++){ltv[i]=et[g.numN-1];//初始化}while (q2.empty()){int top=q.front();//將拓撲排序好的頂點出隊q.pop_front();edge* e=g.al[top].first;while(e){int temp=e->adjvex;//判斷是否需要更新最晚發(fā)生時間//（活動的最晚發(fā)生時間取決于其后繼活動的最晚發(fā)生時間減去活動持續(xù)時間）if (ltv[temp]<ltv[top]+e->weight) ltv[top]=ltv[temp]+e->weight;e=e->next;}}for (int i=0;i<g.numN;i++){edge* e=g.al[i].first;while(e){int temp=e->adjvex;e=et[i];//活動最早時間l=ltv[temp]-e->weight;//最晚開始時間if (e==l)//判斷是否為關(guān)鍵事件......//如果是，進行題目要求的打印或求路徑之和操作e=e->next;}}
}