数据结构-关键路径

介绍

• 在AOV网的基础上，如果用对应边来表示活动持续时间，这种有向图被称为AOE网
• 在AOE网中，入度为0的为源点，出度为0的为汇点，整张网看做是一件事情完成的过程，那么这两个点就是事情的开始和结束。每个活动持续的时间之和称为路径长度，从源点到汇点具有的最大长度的路径就成称为关键路径，关键路径上的活动称为关键活动。

关键路径用来计算整个活动总耗时最短的情况。假如有这样一张AOE网，在完成从1到3的过程中，每件事情需要的时间为边上的权值，那么从开头到结束，由于完成4时2,3也可以同时完成，那么需要的最短时间就是4+1=5

那么，1-4-3就是一条关键路径

不难发现，这条路径是把空余时间“塞满”的路径。假设有一件事持续时间为1h,在12点-15点都可以做，那么这件事的最早开始时间为12点，最晚开始时间为14点，这中间还有两个小时的空隙，时间没有“塞满”，那么就不会构成关键路径

所以，判断关键事件的标准就是其最早开始时间与最晚开始时间是否相等

如何求关键路径

1. 绘制计划图，标注其持续时间
2. 根据各活动的依赖关系，计算其最早开始时间和最晚开始时间
3. 计算每个活动的最早完成时间和最晚完成时间（由2结果可以推导出）
4. 找到最早开始时间与最晚开始时间相等的事件，这些活动构成了关键路径

具体实现

由于计算关键路径之前需要先理清事件的先后关系，所以在找关键路径之前需要先对网图进行拓扑排序，不同的是，我们需要在邻接表中加入代表边权值的值域。

typedef struct edge{int adjvex;//邻接点域，用于储存该顶点对应下标int info;//储存权值int weight;//储存边的权值struct edge* next;//链域，指向下一个邻接点
}edge;
typedef struct vex{int v;//储存顶点int in;//记录入度；edge* first;//边表头指针
}vex,adjlist[MAX];
//储存邻接链表构成的网图信息
typedef struct{adjlist al;int numE,numN;
}graphAL;

拓扑排序过程中也需要加入对时间的判断处理，并额外记录拓扑排序的结果

int et[MAX],lt[MAX];//记录最早时间和最晚时间
bool topo(graphAL g){int n=0;//记录输出的顶点值，判断是否为AOV网deque <int>q;//创建队列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++;//输出的顶点数加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;//继续处理下一个相邻顶点if (et[top]+e->weight>et[temp]) et[temp]=et[top]+e->weight;}}if (n!=g.numN) return false;else return true;
}

关键路径的求取（队列2与最早发生时间数组需要定义在全局或者传入函数中）

void CriticaPath(graphAL g){int e,l;//最早和最晚发生时间topo(g);//首先进行拓扑排序int ltv[g.numN];//最晚发生时间数组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;//判断是否需要更新最晚发生时间//（活动的最晚发生时间取决于其后继活动的最晚发生时间减去活动持续时间）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)//判断是否为关键事件......//如果是，进行题目要求的打印或求路径之和操作e=e->next;}}
}