AOE網
關鍵路徑
求關鍵路徑的算法實作

AOE網是以邊表示活動的有向無環網，在AOE網中，具有最大路徑長度的路徑稱為關鍵路徑，關鍵路徑表示完成工程的最短工期。

1.AOE網

AOE網是一個帶權的有向無環圖。其中用頂點表示事件，弧表示活動，權值表示兩個活動持續的時間。AOE網是以邊表示活動的網。

AOV網描述了活動之間的優先關系，可以認為是一個定性的研究，但是有時還需要定量地研究工程的進度，如整個工程的最短完成時間、各個子工程影響整個工程的程度、每個子工程的最短完成時間和最長完成時間。在AOE網中，通過研究事件和活動之間的關系，可以确定整個工程的最短完成時間，明确活動之間的互相影響，確定整個工程的順利進行。

在用AOE網表示一個工程計劃時，用頂點表示各個事件，弧表示子工程的活動，權值表示子工程的活動需要的時間。在頂點表示事件發生之後，從該頂點出發的有向弧所表示的活動才能開始。在進入某個頂點的有向弧所表示的活動完成之後，該頂點表示的事件才能發生。

對一個工程來說，隻有一個開始狀态和一個結束狀态。是以在AOE網中，隻有一個入度為零的點表示工程的開始，稱為源點；隻有一個出度為零的點表示工程的結束，稱為彙點。

【筆記】AOE網與關鍵路徑1.AOE網2.關鍵路徑3.求關鍵路徑的算法實作

2.關鍵路徑

關鍵路徑是指在AOE網中從源點到彙點路徑最長的路徑。這裡的路徑長度是指路徑上各個活動持續時間之和。在AOE網中，有些活動是可以并行執行的，關鍵路徑其實就是完成工程的最短時間所經過的路徑。關鍵路徑上的活動稱為關鍵活動。

1. 事件 vi 的最早發生時間：從源點到頂點 vi 的最長路徑長度，稱為事件 vi 的最早發生時間，記作ve(i)。求解ve(i)可以從源點ve(0)=0開始，按照拓撲排序規則根據遞推得到：

ve(i)=Max{ve(k)+dut(<k,j>∈)|<k,j>T,1≤i≤n−1}

其中T是所有以第i個頂點為弧頭的弧的集合， dut(<k,j>) 表示弧 <k,j> <script type="math/tex" id="MathJax-Element-7577"> </script>對應的活動的持續時間。

2. 事件 vi 的最晚發生時間：在保證整個工程完成的前提下，活動最遲的開始時間，記作vl(i)。z 求解 vi 的最早發生時間ve(i)的前提vl(n-1)=ve(n-1)下，從彙點開始，向源點推進得到：

vl(i)=Min{vl(k)−dut(<i,k>)|<i,k>∈S,0≤i≤n−2}

其中S是所有以第i個頂點為弧尾的弧的集合， dut(<i,k>) 表示弧 <i,k> <script type="math/tex" id="MathJax-Element-7582"> </script>對應的活動的持續時間。

3.活動 ai 的最早開始時間e(i)：如果弧 <vk,vj> <script type="math/tex" id="MathJax-Element-7584"> </script>表示活動 ai 才開始。是以事件 vk 的最早發生時間也就是活動 ai 的最早開始時間，即e(i)=ve(k)。

4.活動 ai 的最晚開始時間l(i)：在不推遲整個工程完成時間的基礎上，活動 ai 最遲必須開始的事件。如果弧 <vk,vj> <script type="math/tex" id="MathJax-Element-7590"> </script>表示活動 ai ，持續時間為 dut(<k,j>) ，則活動 ai 的最晚開始時間 l(i)=vl(j)−dut(<k,j>) 。

5.活動 ai 的松弛時間：活動 ai 的最晚開始時間域最早開始時間之差就是活動 ai 的松弛時間，記作l(i)-e(i)。

當e(i)=l(i)時，對應的活動 ai 稱為關鍵活動，非關鍵活動提前完成或推遲完成并不會影響到整個工程的進度。

求AOE網的關鍵路徑的算法：

1. 對AOE網中的頂點進行拓撲排序，如果得到的拓撲序列頂點個數小于網中頂點數，則說明網中有環存在，不能求關鍵路徑，終止算法。否則，從源點 v0 開始，求出各個頂點的最早發生時間ve(i)。

2. 從彙點 vn 出發vl(n-1)=ve(n-1)，按照逆拓撲序列求其他頂點的最晚發生時間vl(i)。

3. 由各頂點的最早發生時間ve(i)和最晚發生時間vl(i)，求出每個活動 ai 的最早開始時間e(i)和最晚開始時間l(i)。

4. 找出所有滿足條件e(i)=l(i)的活動 ai ， ai 即是關鍵活動。

【筆記】AOE網與關鍵路徑1.AOE網2.關鍵路徑3.求關鍵路徑的算法實作

關鍵路徑經過的頂點是滿足條件ve(i)==vl(i)，即當事件的最早發生時間與最晚發生時間相等時，該頂點一定在關鍵路徑之上。同樣，關鍵活動者的弧滿足條件e(i)=l(i)，即當活動的最早開始時間域最晚開始時間相等時，該活動一定是關鍵活動。是以，要求關鍵路徑，需要首先求出網中每個頂點的對應事件的最早開始時間，然後推出事件的最晚開始時間和活動的最早、最晚開始時間，最後再判斷頂點是否在關鍵路徑之上，得到網的關鍵路徑。

要求每一個頂點的最早開始時間，首先要将網中的頂點進行拓撲排序。在對頂點進行拓撲排序的過程中，同時計算頂點的最早發生時間ve(i)。從源點開始，由與源點相關聯的弧的權值，可以得到該弧相關聯頂點對應事件的最早發生時間。同時定義一個棧T，儲存頂點的逆拓撲序列。

3.求關鍵路徑的算法實作

采用鄰接表建立上圖所示的有向網，并求網中頂點的拓撲序列，然後計算該有向網的關鍵路徑。

頭檔案棧

#define StackSize 100
typedef struct
{
    DataType stack[StackSize];
    int top;
}SeqStack;

void InitStack(SeqStack *S)    
/*将棧初始化為空棧隻需要把棧頂指針top置為0*/
{
S->top=;   /*把棧頂指針置為0*/
}
int StackEmpty(SeqStack S)   
/*判斷棧是否為空，棧為空傳回1，否則傳回0*/
{
    if(S.top==)            /*判斷棧頂指針top是否為0*/
        return ;           /*當棧為空時，傳回1；否則傳回0*/
    else
        return ;
}
int GetTop(SeqStack S, DataType *e)   
/*取棧頂元素。将棧頂元素值傳回給e，并傳回1表示成功；否則傳回0表示失敗。*/
{
   if(S.top<=)     /*在取棧頂元素之前，判斷棧是否為空*/
{
    printf("棧已經空!\n");
    return ;
}
else
{
    *e=S.stack[S.top-];    /*在取棧頂元素*/
    return ;
}
}
int PushStack(SeqStack *S,DataType e)   
/*将元素e進棧，元素進棧成功傳回1，否則傳回0.*/
{
if(S->top>=StackSize)               /*在元素進棧前，判斷是否棧已經滿*/
{
        printf("棧已滿，不能進棧！\n");
        return ;
}
else
{
        S->stack[S->top]=e;         /*元素e進棧*/
        S->top++;                   /*修改棧頂指針*/
        return ;
}
}
int PopStack(SeqStack *S,DataType *e)
/*出棧操作。将棧頂元素出棧，并将其指派給e。出棧成功傳回1，否則傳回0*/
{
    if(S->top<=)       /*元素出棧之前，判斷棧是否為空*/
    {
        printf("棧已經沒有元素，不能出棧!\n");
        return ;
    }
    else
{
    S->top--;           /*先修改棧頂指針，即出棧*/
        *e=S->stack[S->top];    /*将出棧元素指派給e*/
        return ;
    }
}
int StackLength(SeqStack S)
/*求棧的長度，即棧中元素個數，棧頂指針的值就等于棧中元素的個數*/
{
    return S.top;
}
void ClearStack(SeqStack *S)    
/*将棧初始化為空棧隻需要把棧頂指針top置為0*/
{
S->top=;   /*把棧頂指針置為0*/
}

類型定義

#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef int DataType;           /*棧元素類型定義*/
#include"SeqStack.h"
/*圖的鄰接表類型定義*/
typedef char VertexType[];
typedef int InfoPtr;            /*定義為整型，為了存放權值*/
typedef int VRType;
#define MaxSize 50              /*最大頂點個數*/
typedef enum{DG,DN,UG,UN}GraphKind;     /*圖的類型：有向圖、有向網、無向圖和無向網*/
typedef struct ArcNode          /*邊結點的類型定義*/
{
    int adjvex;                 /*弧指向的頂點的位置*/
    InfoPtr *info;              /*弧的權值*/
    struct ArcNode *nextarc;    /*訓示下一個與該頂點相鄰接的頂點*/
}ArcNode;
typedef struct VNode            /*頭結點的類型定義*/
{
    VertexType data;            /*用于存儲頂點*/
    ArcNode *firstarc;          /*訓示第一個與該頂點鄰接的頂點*/
}VNode,AdjList[MaxSize];
typedef struct                  /*圖的類型定義*/
{
    AdjList vertex;
    int vexnum,arcnum;          /*圖的頂點數目與弧的數目*/
    GraphKind kind;             /*圖的類型*/
}AdjGraph;

有向網的拓撲排序

int ve[MaxSize];                /*ve存放事件最早發生時間*/
int TopologicalOrder(AdjGraph N,SeqStack *T)
/*采用鄰接表存儲結構的有向網N的拓撲排序，并求各頂點對應事件的最早發生時間ve*/
/*如果N無回路，則用用棧T傳回N的一個拓撲序列,并傳回1,否則為0*/
{
    int i,k,count=;
    int indegree[MaxSize];      /*數組indegree存儲各頂點的入度*/
    SeqStack S;
    ArcNode *p;
    /*将圖中各頂點的入度儲存在數組indegree中*/
    for(i=;i<N.vexnum;i++)     /*将數組indegree賦初值*/
        indegree[i]=;
    for(i=;i<N.vexnum;i++)
    {
        p=N.vertex[i].firstarc;
        while(p!=NULL)
        {
            k=p->adjvex;
            indegree[k]++;
            p=p->nextarc;
        }
    }
    InitStack(&S);              /*初始化棧S*/
    printf("拓撲序列：");
    for(i=;i<N.vexnum;i++)
        if(!indegree[i])        /*将入度為零的頂點入棧*/
            PushStack(&S,i);
        InitStack(T);           /*初始化拓撲序列頂點棧*/
        for(i=;i<N.vexnum;i++) /*初始化ve*/
            ve[i]=;
        while(!StackEmpty(S))   /*如果棧S不為空*/
        {
            PopStack(&S,&i);    /*從棧S将已拓撲排序的頂點j彈出*/
            printf("%s ",N.vertex[i].data);
            PushStack(T,i);     /*j号頂點入逆拓撲排序棧T*/
            count++;            /*對入棧T的頂點計數*/
            for(p=N.vertex[i].firstarc;p;p=p->nextarc)  /*處理編号為i的頂點的每個鄰接點*/
            {
                k=p->adjvex;            /*頂點序号為k*/
                if(--indegree[k]==)    /*如果k的入度減1後變為0，則将k入棧S*/
                    PushStack(&S,k);
                if(ve[i]+*(p->info)>ve[k]) /*計算頂點k對應的事件的最早發生時間*/
                    ve[k]=ve[i]+*(p->info);
            }
        }
        if(count<N.vexnum)
        {
            printf("該有向網有回路\n");
            return ;
        }
        else
            return ;
}

有向網的關鍵路徑

int CriticalPath(AdjGraph N)
/*輸出N的關鍵路徑*/
{
    int vl[MaxSize];                /*事件最晚發生時間*/
    SeqStack T;
    int i,j,k,e,l,dut,value,count,e1[MaxSize],e2[MaxSize];
    ArcNode *p;
    if(!TopologicalOrder(N,&T))     /*如果有環存在，則傳回0*/
        return ;
    value=ve[];
    for(i=;i<N.vexnum;i++)
        if(ve[i]>value)
            value=ve[i];            /*value為事件的最早發生時間的最大值*/
        for(i=;i<N.vexnum;i++)     /*将頂點事件的最晚發生時間初始化*/
            vl[i]=value;
        while(!StackEmpty(T))       /*按逆拓撲排序求各頂點的vl值*/
            for(PopStack(&T,&j),p=N.vertex[j].firstarc;p;p=p->nextarc)
            /*彈出棧T的元素,賦給j,p指向j的後繼事件k*/
            {
                k=p->adjvex;
                dut=*(p->info);     /*dut為弧<j,k>的權值*/
                if(vl[k]-dut<vl[j]) /*計算事件j的最遲發生時間*/
                    vl[j]=vl[k]-dut;
            }
        printf("\n事件的最早發生時間和最晚發生時間\ni ve[i] vl[i]\n");
        for(i=;i<N.vexnum;i++)     /*輸出頂點對應的事件的最早發生時間最晚發生時間*/
            printf("%d   %d     %d\n",i,ve[i],vl[i]);
        printf("關鍵路徑為：(");
        for(i=;i<N.vexnum;i++)     /*輸出關鍵路徑經過的頂點*/
            if(ve[i]==vl[i])
                printf("%s ",N.vertex[i].data);
        printf(")\n");
        count=;
        printf("活動最早開始時間和最晚開始時間\n   弧    e   l   l-e\n");
        for(j=;j<N.vexnum;j++)     /*求活動的最早開始時間e和最晚開始時間l*/
            for(p=N.vertex[j].firstarc;p;p=p->nextarc)
            {
                k=p->adjvex;
                dut=*(p->info);     /*dut為弧<j,k>的權值*/
                e=ve[j];            /*e就是活動<j,k>的最早開始時間*/
                l=vl[k]-dut;        /*l就是活動<j,k>的最晚開始時間*/
                printf("%s→%s %3d %3d %3d\n",N.vertex[j].data,N.vertex[k].data,e,l,l-e);
                if(e==l)            /*将關鍵活動儲存在數組中*/
                {
                    e1[count]=j;
                    e2[count]=k;
                    count++;
                }
            }
        printf("關鍵活動為：");
        for(k=;k<count;k++)        /*輸出關鍵路徑*/
        {
            i=e1[k];
            j=e2[k];
            printf("(%s→%s) ",N.vertex[i].data,N.vertex[j].data);
        }
        printf("\n");
    return ;
}

有向網的建立

int LocateVertex(AdjGraph G,VertexType v)
/*傳回圖中頂點對應的位置*/
{
    int i;
    for(i=;i<G.vexnum;i++)
        if(strcmp(G.vertex[i].data,v)==)
            return i;
        return -;
}
void CreateGraph(AdjGraph *N)
/*采用鄰接表存儲結構，建立有向網N*/
{
    int i,j,k,w;
    VertexType v1,v2;                   /*定義兩個弧v1和v2*/
    ArcNode *p;
    printf("請輸入圖的頂點數,邊數(以逗号分隔): ");
    scanf("%d,%d",&(*N).vexnum,&(*N).arcnum);
    printf("請輸入%d個頂點的值:",N->vexnum);
    for(i=;i<N->vexnum;i++)            /*将頂點存儲在頭結點中*/
    {
        scanf("%s",N->vertex[i].data);
        N->vertex[i].firstarc=NULL;     /*将相關聯的頂點置為空*/
    }
    printf("請輸入弧尾、弧頭和權值(以空格作為分隔):\n");
    for(k=;k<N->arcnum;k++)            /*建立邊連結清單*/
    {
        scanf("%s%s%*c%d",v1,v2,&w);
        i=LocateVertex(*N,v1);
        j=LocateVertex(*N,v2);
        /*j為弧頭i為弧尾建立鄰接表*/
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->info=(InfoPtr*)malloc(sizeof(InfoPtr));
        *(p->info)=w;
        /*将p指向的結點插入到邊表中*/
        p->nextarc=N->vertex[i].firstarc;
        N->vertex[i].firstarc=p;
    }
    (*N).kind=DN;
}

有向網的輸出

void DisplayGraph(AdjGraph N)
/*網的鄰接矩陣N的輸出*/
{
    int i;
    ArcNode *p;
    printf("該網中有%d個頂點：",N.vexnum);
    for(i=;i<N.vexnum;i++)
        printf("%s ",N.vertex[i].data);
    printf("\n網中共有%d條弧:\n",N.arcnum);
    for(i=;i<N.vexnum;i++)
    {
        p=N.vertex[i].firstarc;
        while(p)
        {
            printf("<%s,%s,%d> ",N.vertex[i].data,N.vertex[p->adjvex].data,*(p->info));
            p=p->nextarc;
        }
        printf("\n");
    }
}

有向網的銷毀

void DestroyGraph(AdjGraph *N)
/*銷毀無向圖G*/
{
    int i;
    ArcNode *p,*q;
    for(i=;i<N->vexnum;++i)        /*釋放網中的邊表結點*/
    {
        p=N->vertex[i].firstarc;    /*p指向邊表的第一個結點*/
        if(p!=NULL)                 /*如果邊表不為空，則釋放邊表的結點*/
        {
            q=p->nextarc;
            free(p);
            p=q;
        }
    }
    (*N).vexnum=;                  /*将頂點數置為0*/
    (*N).arcnum=;                  /*将邊的數目置為0*/
}

主程式

void main()
{
    AdjGraph N;
    CreateGraph(&N);        /*采用鄰接表存儲結建構立有向網N*/
    DisplayGraph(N);        /*輸出有向網N*/
    CriticalPath(N);        /*求網N的關鍵路徑*/
    DestroyGraph(&N);       /*銷毀網N*/
}

測試結果

【筆記】AOE網與關鍵路徑1.AOE網2.關鍵路徑3.求關鍵路徑的算法實作

【筆記】AOE網與關鍵路徑1.AOE網2.關鍵路徑3.求關鍵路徑的算法實作

1.AOE網

2.關鍵路徑

3.求關鍵路徑的算法實作

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器