视数据结构写代码（46） 关键路径
首先介绍下 概念问题：
与AOV网 相对应的 AOE网(Activity On Edge)，边 表示 活动，顶点表示 事件，边的 权值表示 活动 所需的时间。AOE网 常用于求工程的 最短完成时间 以及哪些活动是影响工程进度的关键。
例如下图：
v1表示 工程的 开始事件，v9表示工程的结束事件。我们将v1(入度为0）叫做源点，v9（出度为0）叫做汇点。AOE网中只有一个源点，一个汇点。否则 出现 环路，无法求出工程的最短用时。
其他顶点 表示 活动的完成，例如V2,表示 活动 a1完成，V5 表示 a5活动 和 a4活动完成。
边上的权 表示 活动 所需事件，例如活动 a1 需要 6天 完成。
AOE网中的事件可以并行处理，所以 最短时间 是从 源点 到汇点的 最长路径，我们称这条路径叫做关键路径。（经过的边的权值之和最大）。
那么怎么求 关键路径呢？我们用逆向思维来看。
完成 工程v9 最快 用时 = v8 事件早完成时间 +4 和 v7最早完成时间+ 2，取最大值。
v8 事件最早完成时间 = v5事件最早完成时间+ 7 和 v6最早完成时间 + 4.取最大值。。。。。。
已知 v1 最早完成时间 为0.
我们用Ve数组 来表示 顶点事件的最早完成时间，dut表示 活动的 完成时间。 得到 一个公式递推公式：
其中 ve(汇点） 就是 工程 最短 用时。
同时，我们在 不耽误 工程进度的前提下 得到 事件的 最晚开始时间。
我们 从汇点 倒推， 得到 一个 事件 的 最晚 开始 时间。
例如 v8的最晚开始时间 = v9(完成时间）- 4，
v5的最晚开始时间 = v7最晚开始时间- 9 和 v8最晚开始时间-7 的 最小值；。。。。
我们 用vl数组，表示 事件的最晚开始时间，也得到一个递推公式：
最晚开始时间 = 最早开始时间 的 活动叫做 关键活动。
求最短用时，是一个 拓扑排序的 过程。
求 关键 活动 是 一个 逆向 拓扑排序的过程。
下面上代码：（代码是以图的邻接表为 图的 表示法的）
//拓扑排序，并将 拓扑排序 插入 栈中
//ve 数组 成员 初始值 为0,计算出顶点事件的最早开始时间.
bool topoLogicalOrder(Graph g,int * ve,linkStack * topoStack){
//求所有顶点的入度
int degreeArray[MAX_VERTEX_NUM] ={0};
for (int i = 0; i < g.vexNum; i++){
ArcNode * next = g.list[i].head->nextArc;
for (; next != NULL; next = next->nextArc){
int index = next->adjVex;
degreeArray[index] ++;
}
}
//度为0的节点入栈
linkStack stack;
stackInit(&stack);
for (int i = 0; i < g.vexNum; i++){
if (degreeArray[i] == 0){
stackPush(&stack,i);
}
}
//循环删除度为0的节点
while (!stackEmpty(stack)){
int top;
stackPop(&stack,&top);
//将拓扑排序 插入 栈中
stackPush(topoStack,top);
ArcNode * next = g.list[top].head->nextArc;
for (;next != NULL; next = next->nextArc){
int index = next->adjVex;
if (--degreeArray[index] == 0){
stackPush(&stack,index);
}
if (ve[top] + next->weight > ve[index]){
ve[index] = ve[top] + next->weight;
}
}
}
stackDestory(&stack);
//返回是否存在环路
return stackLen(*topoStack) == g.vexNum ? false : true;
}
//求AOE网的 关键路径
void criticalPath(Graph g){
int ve[MAX_VERTEX_NUM] = {0};//顶点事件的最早开始时间
linkStack topoStack;
stackInit(&topoStack);
if (topoLogicalOrder(g,ve,&topoStack)){//获得逆拓扑排序
printf("图中 存在环路，无法求出 关键路径\n");
}
int vl[MAX_VERTEX_NUM];//顶点事件的最晚开始时间.
for (int i = 0; i < g.vexNum; i++){//初始化为工程完成时间.
vl[i] = ve[g.vexNum-1];
}
while (!stackEmpty(topoStack)){
int top;
stackPop(&topoStack,&top);
ArcNode * next = g.list[top].head->nextArc;
for (;next != NULL; next=next->nextArc){
int inIndex = next->adjVex;
if (vl[top] > vl[inIndex] - next->weight){
vl[top] = vl[inIndex] - next->weight;
}
}
}
printf("工程最短用时：%d\n",ve[g.vexNum-1]);
printf("-------------图的关键活动------------\n");
for (int i = 0; i < g.vexNum; i++){
ArcNode * next = g.list[i].head->nextArc;
for (;next != NULL;next = next->nextArc){
int inIndex = next->adjVex;
if (ve[i] == vl[inIndex]-next->weight){
printf("%c ~ %c,耗费时间为：%d\n",g.list[i].vexName,g.list[inIndex].vexName,next->weight);
}
}
}
printf("\n");
stackDestory(&topoStack);
}
代码运行截图：