[图](11)关键路径

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

AOV网的特点：

• 用顶点表示事件
• 用弧表示活动
• 用权值表示活动时间
• AOE网的图没有环

AOE网的性质：

⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；

⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

关键活动：关键路径上的活动称为关键活动。关键活动：ee[i]=el[i]的活动

　　由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

关键路径可能不止一条，重要的是找到关键活动

与关键活动有关的量：

⑴ 事件的最早发生时间ve[k]

　　ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。

⑵ 事件的最迟发生时间vl[k]

　　vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

⑶ 活动的最早开始时间e[i]

　　若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：e[i]=ve[k]

⑷ 活动的最晚开始时间l[i]

　　活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：l[i]=vl[j]-len<vk, vj>

图示求几个量如下所示：

其算法演示如下所示：

其代码如下所示：

#define _CRT_SECURE_NO_WARNINGS
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#include<stdio.h>
#include<stdlib.h>

typedef int Status;
typedef int BOOL;
typedef enum { DG, DN, UDG, UDN }GraphKind;
#define MAX_VERTEX_NUM 20
typedef int InfoType;
typedef int VertexType;

typedef struct ArcNode {
    int adjvex;
    InfoType weight;
    struct ArcNode* nextarc;
}ArcNode;

typedef struct VNnde {
    int in;
    VertexType data;
    ArcNode* firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
    int* ve, * vl;
    GraphKind Kind;
}ALGraph;

int LocateVex(ALGraph* G, int e) {
    for (int i = 0; i < G->vexnum; i++)
        if (G->vertices[i].data == e) return i;
    return -1;
}

Status Print_AdjList(ALGraph* G) {

    for (int i = 0; i < G->vexnum; i++) {
        ArcNode* p;
        printf("in：%d[V(%d)]：", G->vertices[i].in, G->vertices[i].data);
        p = G->vertices[i].firstarc;
        while (p) {
            printf("(%d,%d)%d-->", G->vertices[i].data, p->adjvex, p->weight);
            p = p->nextarc;
        }
        printf("\n");
    }

    return OK;
}
Status CriticalPath(ALGraph* G) {//根据事件最早发生事件ve和最迟发生事件vl的量求出关键路径
    //ee代表活动最找发生时间，el代表活动最迟发生时间
    ArcNode* p;
    int OutVex;
    for (int inVex = 0; inVex < G->vexnum; inVex++) {
        p = G->vertices[inVex].firstarc;
        while (p) {
            OutVex = p->adjvex;
            int ee = G->ve[inVex];
            int el = G->vl[OutVex] - p->weight;
            if (ee == el)
                printf("<%d,%d>、", inVex, OutVex);
            p = p->nextarc;
        }
    }
    return OK;
}
Status EventLastTime(ALGraph* G) {
    int InVex;
    int OutVex;
    ArcNode* p;
    //事件最迟发生时间
    for (int i = G->vexnum - 1; i >= 0; i--)
        G->vl[i] = G->ve[G->vexnum - 1];//根据公式初始化vl数组

    for (int i = G->vexnum - 1; i >= 0; i--) {
        InVex = G->vertices[i].data;
        p = G->vertices[i].firstarc;
        while (p) {
            OutVex = p->adjvex;
            if (G->vl[OutVex] - p->weight < G->vl[InVex])
                G->vl[InVex] = G->vl[OutVex] - p->weight;
            p = p->nextarc;
        }
    }
    return OK;
}

Status TopSort(ALGraph* G) {
    //拓扑排序
    int* Stack = (int*)malloc(sizeof(int) * G->vexnum);//栈作为记录入度量为0的顶点
    int top = -1;

    for (int i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].in == 0) {
            top++;
            Stack[top] = i;//记录其顶点序号
        }
    }

    int OutVex, InVex;
    ArcNode* p;

    //初始状态的事件最早发生时间，全为0
    for (int i = 0; i < G->vexnum; i++) G->ve[i] = 0;

    //利用其拓扑序列计算其事件最早发生事件
    while (top != -1) {
        OutVex = Stack[top--];//出度边等于栈顶元素，按照其约定，需要删去其所有出度边

        p = G->vertices[OutVex].firstarc;
        printf("%d ", G->vertices[OutVex].data);//打印顶点，打印其拓扑序列
        while (p) {
            InVex = p->adjvex;
            G->vertices[InVex].in--;//不改变其逻辑结构，为拓扑排序只改变其入度量

            if (G->vertices[InVex].in == 0) Stack[++top] = InVex;

            if (p->weight + G->ve[OutVex] > G->ve[InVex])//计算事件的最早发生时间
                //由前一个时间的最早开始时间加上前一个时间所需要的时间
                //判断是否大于当前事件的最早开始时间
                //若大于，则更新当前事件的最早开始时间
                G->ve[InVex] = p->weight + G->ve[OutVex];
            p = p->nextarc;
        }
    }
    EventLastTime(G);
    CriticalPath(G);
    return OK;
}

Status CreateDN(ALGraph* G) {
    char tem;//过滤空格符
    printf("Please Input Vexnum and Arcnum：");
    scanf("%d,%d%c", &G->vexnum, &G->arcnum, &tem);
    if (G->vexnum < 1 || G->arcnum < 1) return ERROR;

    printf("Please Input VexSet：");//初始化顶点表
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d%c", &G->vertices[i].data, &tem);
        G->vertices[i].firstarc = NULL;
        G->vertices[i].in = 0;//入度量均初始化为0
    }

    G->ve = (int*)malloc(sizeof(int) * G->vexnum);//事件最早发生时间
    G->vl = (int*)malloc(sizeof(int) * G->vexnum);//事件最迟发生时间

    int vi, vj;
    int InVex, OutVex, weight;//入度顶点、出度顶点、权值
    ArcNode* p;
    //创建邻接表
    for (int i = 0; i < G->arcnum; i++) {
        printf("Please InVex 、OutVex and Weight：");
        scanf("%d,%d,%d%c", &vi, &vj, &weight, &tem);
        OutVex = LocateVex(G, vi);
        InVex = LocateVex(G, vj);
        if (InVex == -1 || OutVex == -1) return ERROR;

        p = (ArcNode*)malloc(sizeof(ArcNode));//创建结点

        p->adjvex = InVex;
        p->weight = weight;
        G->vertices[InVex].in++;//其入度顶点的入度量自增

        p->nextarc = G->vertices[OutVex].firstarc;
        G->vertices[OutVex].firstarc = p;
    }

    Print_AdjList(G);//打印邻接表
    return OK;
}
int main() {
    ALGraph G;
    CreateDN(&G);
    TopSort(&G);
    system("pause");

    return 0;
}
/*
测试数据
9,11
0
1
2
3
4
5
6
7
8
0,1,6
0,2,4
0,3,5
1,4,1
2,4,1
3,5,2
4,6,9
4,7,7
5,7,4
6,8,2
7,8,4
*/

实践已经证明：用AOE网来估算某些工程完成的时间是非常有用的，实际上，求关键路径的方法本身最初就是与维修和建造工程一起发展的，但是，由于网中各项活动是互相牵连的，因此，影响关键活动的因素亦是多方面的

任何一项活动持续时间的改变都会影响关键路径的改变，只有在不改变网的关键路径的情况下，提高活动的速度才有效

另一方面，若网中有几条关键路径，那么，单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上活动的速度

本文链接：