数据结构-求关键路径和关键活动

情境引入：

在前面我们学过AOV网，AOV网用来确定活动之间的优先顺序。

在实际应用中，活动之间除了先后顺序外，还有时间上的约束。

在一个表示工程的带权有向图中，用顶点表示时间，用边表示活动，边上的权值表示活动的持续时

间，这样的有向图被叫做：“AOE”网。

通常，AOE网可以用来估测工程的完成时间。

AOE网中，入度为0的顶点叫做：“源点”，出度为0的顶点叫做：“汇点”。

为此我们得到AOE网的两条重要性质：

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

2.只有在进入某时间的全部活动结束后，该事件才能开始。

因此完成工程的最短时间就是从源点到汇点的最短路径长度。具有最长长度的路径被叫作：“关键

路径”，路径长度是指路径上的各权度之和。关键路径上的活动被叫作关键活动。

而想要缩短工期，则必须对关键活动下手，为此我们可以设计一个算法来实现这个功能。

代码部分：

#include
#include
#define MAX 100
 
typedef struct ArcNode{
	int adjvex;
	int weight;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
	char vertex;
	ArcNode *firstarc;
}VNode;
typedef VNode Adjlist[MAX];
typedef struct ALGraph{
	Adjlist adjlist;
	int vexnum;
	int arcnum;
}ALGraph;
 
int LocateVertex(ALGraph *G,char v)	//查询顶点在邻接图中的位置 
{
	int num;
	for(num=0;numvexnum;num++)
		if(G->adjlist[num].vertex == v)
			return num;
	return -1;
}
 
void CreateALGraph(ALGraph *G)		//创建邻接图 
{
	int i,weight;
	int num1,num2;
	char v1,v2;
	printf("请输入顶点数和边数:\n");
	scanf("%d %d",&G->vexnum,&G->arcnum);
	getchar();
	printf("请输入:{%d}个顶点\n",G->vexnum);
	for(i=0;ivexnum;i++){
		scanf("%c",&G->adjlist[i].vertex);
		G->adjlist[i].firstarc = NULL;
	}
	getchar();
	printf("请输入:{%d}条边,格式->(v1 v2 权值)\n",G->arcnum);
	for(i=0;iarcnum;i++){
		scanf("%c %c %d",&v1,&v2,&weight);
		getchar();
		num1 = LocateVertex(G,v1);
		num2 = LocateVertex(G,v2);
		if(num1 == -1 || num2 == -1){
			printf("失败.num1->{%d}、num2->{%d}\n",num1,num2);
			i = i - 1;
			continue;
		}
		else{
			ArcNode *tmp = (ArcNode*)malloc(sizeof(ArcNode));
			tmp->adjvex = num2;
			tmp->weight = weight;
			tmp->nextarc = G->adjlist[num1].firstarc;
			G->adjlist[num1].firstarc = tmp;
			printf("成功.\n");
		}
	} 
}
 
void FindInDegree(ALGraph *G,int *indegree)		//查找图中所有顶点入度 
{
	ArcNode *tmp = NULL;
	int i;
	for(i=0;ivexnum;i++){
		indegree[i] = 0;
	}	
	for(i=0;ivexnum;i++){
		tmp = G->adjlist[i].firstarc;
		while(tmp){
			indegree[tmp->adjvex]++;
			tmp = tmp->nextarc;
		}
	}
}
 
void CriticalPath(ALGraph *G,int n)		//求关键路径函数,n是图中顶点个数 
{
	ArcNode *tmp = NULL;
	int i,v,weight,num,indegree[n];	
	int ee,el,sum = 0;	//ee和el指针 
	int ve[n],vl[n];		//ve和vl数组 
	int top1 = 0,top2 = 0;		//top1和top2两个栈顶指针 
	FindInDegree(G,indegree);		//top1是正向拓扑排序指针,top2是逆向拓扑排序指针 
	for(i=0;ivexnum;i++)		//最早发生时间ve数组赋初值0 
		ve[i] = 0;	
	for(i=0;ivexnum;i++){		//入度为0的顶点入栈(正序栈) 
		if(indegree[i] == 0){
			indegree[i] = top1;
			top1 = i + 1;
		}
	}
	while(top1!=0){		//正序栈出栈，同时也是拓扑排序遍历 
		v = top1 - 1;
		top1 = indegree[v];		//出栈 
		indegree[v] = top2;		//构建逆序栈，为逆拓扑排序准备 
		top2 = v + 1;			//逆拓扑栈顶指针加一 
		tmp = G->adjlist[v].firstarc;
		while(tmp){		//进入单个邻接单元的nextarc循环中 
			weight = tmp->weight;
			num = tmp->adjvex;
			if(ve[v] + weight > ve[num]){		//永远使ve[i]中所存的是当前消去顶点后的最大值. 
				ve[num] = ve[v] + weight;
			}
			if(--indegree[num] == 0){	//减去一个顶点,对应边也要减去,因此邻接边的入度要减少1
				indegree[num] = top1;	//如果减1后等于0,需要入栈成为一个新的拓扑点 
				top1 = num + 1;
			}
			tmp = tmp->nextarc;
		}
	}
	for(i=0;ivexnum;i++){
		vl[i] = ve[top2-1];		//vl数组初始化,全部用逆拓扑排序的起点。 
	}
	while(top2!=0){
		v = top2 - 1;		//出栈,逆拓扑排序
		top2 = indegree[v];		
		tmp = G->adjlist[v].firstarc;		
		while(tmp){
			num = tmp->adjvex;
			weight = tmp->weight;
			if(vl[num] - weight < vl[v]){		//vl中所存的一定是最小的数值 
				vl[v] = vl[num] - weight;
			}
			tmp = tmp->nextarc;
		}
	}
	for(i=0;ivexnum;i++){		//关键路径遍历循环 
		tmp = G->adjlist[i].firstarc;
		while(tmp){
			num = tmp->adjvex;
			weight = tmp->weight;
			ee = ve[i];		//ee==ve 
			el = vl[num] - weight;		//el==vl - weight 
			if(ee == el){		//如果ee==el那么说明是一个关键路径 
				printf("边<%c,%c>输出,权值为:{%d}\n",G->adjlist[i].vertex,G->adjlist[num].vertex,weight);
				sum += weight;
			}
			tmp = tmp->nextarc;
		}
	}
	printf("因此关键路径长度为:{%d}\n",sum);
}
 
 
int main()
{
	ALGraph G;
	CreateALGraph(&G);
	CriticalPath(&G,G.vexnum);
	return 0;
}

例子：

上面的例子共ABCDEFGHK九个事件（顶点），共a1->a12（12个活动）。

算法思想：

在知道AOE网的两条性质后，我们很容易的想到算法：

我们先定义下面四个“参量”：

事件的最早发生时间->“ve”，事件的最迟发生时间->"vl"，活动的最早发生时间->"ee"，活动的最迟

发生时间->"el"。

1.事件的最早发生时间

ve指的是从源点到顶点V的最长路径长度

这个长度决定了所有从顶点ve发出的活动能够开工的最早时间。

因此ve的大小取决于最慢的那个活动，也就是：

ve[k] = max{ve[j] + dut}

例如上面的例子，我们可以得到下面的最长路径长度:

2.事件的最晚发生时间

事件的最晚发生时间通俗点来说，就是在查找到事件的最早发生时间之后，通过逆序的顺序，依次

减去各边最大值求得。

公式为:

vl[j] = min{ve[k] - dut}

根据上面的的解释，我们可以得到这个例子的vl如下：

3.活动的最早发生时间

活动的最早发生时间等于事件的最早发生时间，这是由AOE网的性质决定的，只有当某个事件发生

了，某个活动才会发生。

因此我们可以得到:

4.活动的最晚发生时间

活动的最晚发生时间是指，在不推迟整个工期的前提下的时间。

因此，有公式：

el[i] = {vl[k] - dut}

通过上式，我们可以得到：

验证部分：