前言

在學習了最小路徑的最小最短概念及拓撲排序的頂點先后順序概念后，今天我們來了解另外一個圖的應(yīng)用----關(guān)鍵路徑。通過關(guān)鍵路徑的學習我們需要理解在實際生活中例如工程的每個步驟的時間點規(guī)劃問題。

概念

例如，造一輛汽車，我們需要先制造各種各樣的零件，然后組裝成一輛完整的汽車。
那么在組裝工作開始前，各部件得先制造出來，假如造一個輪子，需要0.5天時間，造一個發(fā)動機需要3天時間，早一個底盤需要2天時間，然后將各個部件集中到一起需要0.5天，組裝好汽車需要2天時間，那么從開始制造到組裝完成需要多長時間呢？

造汽車流程時間圖

1. AOE網(wǎng)：在一個表示工程的帶權(quán)有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權(quán)值表示活動的持續(xù)時間，這種有向圖的邊表表示活動的網(wǎng)。沒有入邊的頂點稱為始點或源點，沒有出邊的頂點稱為終點或匯點，正常情況下，AOE網(wǎng)只有一個源點和一個匯點。
2. 路徑上各個活動持續(xù)的時間之和稱為路徑長度。
3. 從開始點到結(jié)束點具有最大的路徑叫關(guān)鍵路徑。
4. 在關(guān)鍵路徑上的活動叫做關(guān)鍵活動。

例子

如下圖所示例子，設(shè)計算法計算出源點到匯點的關(guān)鍵路徑。

在計算之前，需要先了解求解過程中的幾個核心參數(shù)：

• 事件最早發(fā)生時間etv（earliest time of vertex）：頂點Vk的最早發(fā)生時間。
• 事件最晚發(fā)生時間ltv（latest time of vertex）：頂點Vk的最晚發(fā)生時間，也就是每個頂點對應(yīng)的事件最晚需要開始的時間，超出時間將會耽誤整個工期。
• 活動的最早開工時間ete（earliest time of edge）：弧Ak的最早發(fā)生時間。
• 活動的最晚開工時間lte（latest time of edge）：弧Ak的最晚發(fā)生時間，也就是不推遲工期的最晚開工時間。

思路

求事件的最早發(fā)生時間etv（針對頂點）的過程，就是從頭到尾去找拓撲序列的過程，所以求解關(guān)鍵路徑之前，我們需要利用拓撲排序的思想去實現(xiàn)。
同樣的關(guān)鍵路徑的求解鄰接表的方式更適合，初始化鄰接表如下：

鄰接表

演算過程

在最小路徑等概念中我們是求最小路徑，但是關(guān)鍵路徑的求解求的是最大路徑，比如造汽車圖中的（開始-->造發(fā)動機-->部件集中-->組裝完成 ）就是關(guān)鍵路徑，因為用時最長，但是造發(fā)動機又是不得不走的路徑。

求解etv（事件最早發(fā)生時間）

步驟一： 以V0源點開始，得到etv[1] = 3，即頂點V1事件的最早發(fā)生時間為V0-->V1的弧長3，同理etv[2] = 4，那么etv[3] = max(3+5,4+8) = 12，意思就是V3事件最早發(fā)生時間為12，可以理解為V3事件的開始需要滿足V1和V2兩個零件的完成，才能開始V3事件，所以V3需要等待V2更久，取兩條路徑中的最大值12。

1. etv[0] = 0；
2. etv[k] = mak { etv[i] + len<Vi, Vk> } , <Vi, Vk>屬于圖中弧集合中的一條。

步驟二：重復利用以上公式，計算得到如下etv數(shù)組：

etv

求解ltv（事件最晚發(fā)生時間）

事件最晚發(fā)生時間，在不耽誤工期的情況下，比如上面造零件一樣，造零件的最長時間內(nèi)，各個零件時間安排是隨機的，在最長時間造發(fā)動機3天時間內(nèi)，可以第一個半天就把輪子造好，也可以在3天內(nèi)的最后一個半天把輪子造好，只要不影響部件集中及后續(xù)工期，都是滿足條件的。那么造輪子這個事件最晚發(fā)生時間就是2.5天的時候，再晚就會影響后續(xù)工期。

步驟一：因為etv[9]為圖中最大路徑27，所以匯點的最晚開始時間就是27，也就是到達匯點之前，必須經(jīng)過27的權(quán)值。所以初始化ltv為etv最后一個事件的時間27。將源點到匯點的頂點序號依次入棧stack，從后往前開始比較計算。
步驟二：首次出棧的gettop = 9，但由于V9沒有弧表，則沒有相關(guān)的ltv更新。
步驟三：出棧gettop = 8，由于V8指向V9，ltv[9] = 27, ltv[8] = min(27, 27 - 3) = 24, V8-->V9弧長為3。更新ltv數(shù)組。
步驟四：出棧gettop = 7， 由于V7指向V8， ltv[8] = 24, ltv[7] = min(24, 24 - 5) = 19, 更新ltv數(shù)組。依次這么比較計算得到最終ltv結(jié)果如下：

ltv

演算公式如下：

1. ltv[k] = etv[k] , 當 k = n-1 時；
2. ltv[k] = min { ltv[i] - len<Vi,Vj> }，當 k < n - 1, <Vi,Vj>屬于弧的集合。

ete（活動最早開工時間）& lte（活動最晚開工時間）

思路：

• 活動最早開工時間即弧Ak的最早發(fā)生時間。表示活動<Vk,Vj>的最早開工時間，是針對這條弧的說的，而這條弧的弧尾頂點Vk的事件發(fā)生了，它才可以發(fā)生，因為ete[k] = etv[k]。
• 活動最晚開工時間即弧<Vk,Vj>的最晚開工時間，但此活動再晚不能等Vj事件發(fā)生了才開始，而是必須在Vj事件之前發(fā)生，所以lte = ltv[j] - len<Vk, Vj>。
• 判斷ete 與 lte 是否相等，相等就意味著活動之間沒有任何空余時間，那么這條弧必定在關(guān)鍵路徑中，此次活動稱為關(guān)鍵活動，否則不是。

步驟一：著手V0頂點，指向V1， 所以ete = etv[0] = 0，lte = ltv[0] - 3 = 7 - 3 = 4, 判斷ete != lte ,說明<V0, V1>不是關(guān)鍵活動。同時V0指向V2，所以ete = etv[0] = 0，lte = ltv[2] - 4 = 4 - 4 = 0, 判斷ete == lte ,說明<V0, V2>是關(guān)鍵活動。

步驟二：繼續(xù)來到V1頂點，先處理指向V4的弧，則ete = etv[1] = 3, lte = ltv[4] - 6 = 15 - 6 = 9，發(fā)現(xiàn)ete != lte， 說明<V1,V4> 不是關(guān)鍵活動。再處理指向的V3的弧，ete = etv[1] = 3, lte -= ltv[3] - 5 = 12 - 5 = 7, ete != lte ,說明<V1, V3>也不是關(guān)鍵活動。依此類推后續(xù)的弧，最終得到關(guān)鍵路徑為下圖中的綠色路徑：

代碼

#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */

/* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/* 鄰接表結(jié)構(gòu)****************** */
//邊表結(jié)點
typedef struct EdgeNode
{
    //鄰接點域，存儲該頂點對應(yīng)的下標
    int adjvex;
    //用于存儲權(quán)值，對于非網(wǎng)圖可以不需要
    int weight;
    //鏈域，指向下一個鄰接點
    struct EdgeNode *next;
}EdgeNode;

//頂點表結(jié)點
typedef struct VertexNode
{
    //頂點入度
    int in;
    //頂點域，存儲頂點信息
    int data;
    //邊表頭指針
    EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    //圖中當前頂點數(shù)和邊數(shù)
    int numVertexes,numEdges;
}graphAdjList,*GraphAdjList;

/* **************************** */

/* 關(guān)于AOE網(wǎng)圖的存儲代碼段-Begin */
//1.完成AOE網(wǎng)圖關(guān)于鄰接矩陣的存儲
void CreateMGraph(MGraph *G)/* 構(gòu)件圖 */
{
    int i, j;
    /* printf("請輸入邊數(shù)和頂點數(shù):"); */
    G->numEdges=13;
    G->numVertexes=10;

    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        G->vexs[i]=i;
    }

    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j]=INFINITYC;
        }
    }

    G->arc[0][1]=3;
    G->arc[0][2]=4;
    G->arc[1][3]=5;
    G->arc[1][4]=6;
    G->arc[2][3]=8;
    G->arc[2][5]=7;
    G->arc[3][4]=3;
    G->arc[4][6]=9;
    G->arc[4][7]=4;
    G->arc[5][7]=6;
    G->arc[6][9]=2;
    G->arc[7][8]=5;
    G->arc[8][9]=3;

}


//2.將鄰近矩陣轉(zhuǎn)化成鄰接表
void CreateALGraph(MGraph G,GraphAdjList *GL){

    int i,j;
    EdgeNode *e;

    *GL = (GraphAdjList)malloc(sizeof(graphAdjList));

    (*GL)->numVertexes=G.numVertexes;
    (*GL)->numEdges=G.numEdges;

    //讀入頂點信息，建立頂點表
    for(i= 0;i <G.numVertexes;i++)
    {
        (*GL)->adjList[i].in=0;
        (*GL)->adjList[i].data=G.vexs[i];
        //將邊表置為空表
        (*GL)->adjList[i].firstedge=NULL;
    }

    //建立邊表
    for(i=0;i<G.numVertexes;i++)
    {
        for(j=0;j<G.numVertexes;j++)
        {
            if (G.arc[i][j]!=0 && G.arc[i][j]<INFINITYC)
            {
                e=(EdgeNode *)malloc(sizeof(EdgeNode));
                //鄰接序號為j
                e->adjvex=j;
                e->weight=G.arc[i][j];
                //將當前頂點上的指向的結(jié)點指針賦值給e
                e->next=(*GL)->adjList[i].firstedge;
                //將當前頂點的指針指向e
                (*GL)->adjList[i].firstedge=e;
                (*GL)->adjList[j].in++;

            }
        }
    }
}
/* 關(guān)于AOE網(wǎng)圖的存儲代碼段-End! */
int *etv,*ltv; /* 事件最早發(fā)生時間和最遲發(fā)生時間數(shù)組，全局變量 */
int *stack2;   /* 用于存儲拓撲序列的棧 */
int top2;       /* 用于stack2的指針*/

//拓撲排序
Status TopologicalSort(GraphAdjList GL){

    //若GL無回路,則輸出拓撲排序序列且返回狀態(tài)OK, 否則返回狀態(tài)ERROR;
    EdgeNode *e;
    int i,k,gettop;
    //棧指針下標;
    int top = 0;
    //用于統(tǒng)計輸出的頂點個數(shù).作為拓撲排序是否存在回路的判斷依據(jù);
    int count = 0;
    //建棧,將入度in = 0的頂點入棧;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));

    //遍歷頂點表上入度in ?= 0 入棧
    for (i = 0; i < GL->numVertexes;i++) {
        //printf("%d %d\n",i,GL->adjList[i].in);
        if ( 0 == GL->adjList[i].in ) {
            stack[++top] = i;
        }
    }

    //* stack2 的棧指針下標
    top2 = 0;
    //* 初始化拓撲序列棧
    stack2 = (int *)malloc(sizeof(int) * GL->numVertexes);
    //* 事件最早發(fā)生時間數(shù)組
    etv = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));
    //* 初始化etv 數(shù)組
    for (i = 0 ; i < GL->numVertexes; i++) {
        //初始化
        etv[i] = 0;
    }

    printf("TopologicSort:\t");
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count++;

        //將彈出的頂點序號壓入拓撲排序的棧中;
        stack2[++top2] = gettop;
        
        //例如gettop為V0 ,那么與V0相連接的結(jié)點就有etv[1] = 3; etv[2] = 4;
        //例如gettop為V1 ,那么與V1連接的結(jié)點就有etv[4]= 3+6=9; etv[3] = 8;
        //例如gettop為V2 ,那么與V2連接的結(jié)點就有etv[5]= 4+7=11; etv[3] = 12;
        //例如gettop為V3 ,那么與V3連接的結(jié)點就有etv[4]= 12+3=15;
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            k = e->adjvex;
            
            //將i頂點連接的鄰接頂點入度減1,如果入度減一后為0,則入棧
            if(!(--GL->adjList[k].in))
                stack[++top] = k;

            //求各頂點事件的最早發(fā)生的時間etv值
            //printf("etv[gettop]+e->weight = %d\n",etv[gettop]+e->weight);
            //printf("etv[%d] = %d\n",k,etv[k]);
            if ((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }

    }
    printf("\n");
    
    //打印etv(事件最早發(fā)生時間數(shù)組)
//    for (i = 0; i < GL->numVertexes; i++) {
//        printf("etv[%d] = %d\n",i,etv[i]);
//    }
//    printf("\n");
    
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
    return OK;
}

//求關(guān)鍵路徑, GL為有向網(wǎng),則輸出G的各項關(guān)鍵活動;
void CriticalPath(GraphAdjList GL){
    EdgeNode *e;
    int i,gettop,k,j;
    
    //聲明活動最早發(fā)生時間和最遲發(fā)生時間變量;
    int ete,lte;
    
    //求得拓撲序列,計算etv數(shù)組以及stack2的值
    TopologicalSort(GL);
   
    //打印etv數(shù)組(事件最早發(fā)生時間)
    printf("etv:\n");
    for(i = 0; i < GL->numVertexes; i++)
        printf("etv[%d] = %d \n",i,etv[i]);
    printf("\n");
    
    //事件最晚發(fā)生時間數(shù)組
    ltv = (int *)malloc(sizeof(int) * GL->numVertexes);
   
    //初始化ltv數(shù)組
    for (i = 0; i < GL->numVertexes; i++) {
        //初始化ltv數(shù)組. 賦值etv最后一個事件的值
        ltv[i] = etv[GL->numVertexes-1];
        //printf("ltv[%d] = %d\n",i,ltv[i]);
    }
    
    //計算ltv(事件最晚發(fā)生時間) 出棧求ltv
    while (top2 != 0) {
        
        //出棧(棧頂元素)
        gettop = stack2[top2--];
        
        //找到與棧頂元素連接的頂點; 例如V0是與V1和V2連接
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            //獲取與gettop 相連接的頂點
            k = e->adjvex;
            //計算min(ltv[k]-e->weight,ltv[gettop])
            if (ltv[k] - e->weight < ltv[gettop]) {
                //更新ltv 數(shù)組
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }
    
    //打印ltv 數(shù)組
    printf("ltv:\n");
    for (i = 0 ; i < GL->numVertexes; i++) {
        printf("ltv[%d] = %d \n",i,ltv[i]);
    }
    
    printf("\n");
    //求解ete,lte 并且判斷l(xiāng)te與ete 是否相等.相等則是關(guān)鍵活動;
    //2層循環(huán)(遍歷頂點表,邊表)
    for(j=0; j<GL->numVertexes;j++)
    {
        for (e = GL->adjList[j].firstedge; e; e = e->next) {
            //獲取與j連接的頂點;
            k = e->adjvex;
            //ete 就是表示活動 <Vk, Vj> 的最早開工時間, 是針對這條弧來說的.而這條弧的弧尾頂點Vk 的事件發(fā)生了, 它才可以發(fā)生. 因此ete = etv[k];
            ete = etv[j];
            //lte 表示活動<Vk, Vj> 的最晚開工時間, 但此活動再晚也不能等Vj 事件發(fā)生才開始,而是必須在Vj 事件之前發(fā)生. 所以lte = ltv[j] - len<Vk, Vj>.
            lte = ltv[k]-e->weight;
            //如果ete == lte 則輸出j,k以及權(quán)值;
            if (ete == lte) {
                printf("<%d-%d> length:%d\n",GL->adjList[j].data, GL->adjList[k].data, e->weight);
            }
        }
    }
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 關(guān)鍵路徑的求解!\n");
    MGraph G;
    GraphAdjList GL;
    CreateMGraph(&G);
    CreateALGraph(G,&GL);
    
    //拓撲排序
    //TopologicalSort(GL);
    
    //關(guān)鍵路徑
    CriticalPath(GL);

    return 0;
}