《大话数据结构》之关键路径算法

àì夳堔傛蜴生んèń 2022-08-17 14:10 155阅读 0赞

关键路径算法是在AOE网中找出完成所有活动耗时最长的路径的方法。

程序中涉及的结构：

typedef char VertexType;
    typedef int EdgeType;
    
    //邻接节点结构
    typedef struct EdgeNode
    {
    	int adjvex;
    	EdgeType weight;
    	struct EdgeNode *next;
    }EdgeNode;
    
    //顶点节点列表
    typedef struct VertexNode
    {
    	VertexType data;
    	EdgeNode *firstedge;
    }VertexNode,AdjList[MAXVEX];
    
    //图的总述结构
    typedef struct 
    {
    	AdjList adjList;
    	int numVertexes,numEdges;
    }GraphAdjList;

关键路径的算法是在AOV网的拓补排序下完成的。

拓补排序基本思想就是：逐步找出AOV网中入度为0的节点。输出该节点后将与它相邻的节点的入度减一，如果此时该节点入度为零就输出。

输出入度为0的节点过程中，可以借用栈等数据结构完成输出。

**PS：拓补序列不为1，同一个网可以有多个不同的拓补序列。**

拓补排序代码如下：

int *etv,*ltv;
    int *stack2;
    int top2;
    
    /*
    利用拓补排序判断一个网是否有环路
    */
    Status TopologicalSort(GraphAdjList GL)
    {
    	EdgeNode *e;
    	int i,k,gettop;
    	int top = 0;
    	int count = 0;
    	int *stack;
    	stack = (int *)malloc(GL->numVertexes * sizeof(int));
    	for(i=0;i<GL->numVertexes;i++)
    	{
    		if(0 == GL->adjLIst[i].in)
    		{
    			top = top + 1;
    			stack[top] = i;
    			
    		}
    	}
    	top2 = 0;
    	ltv = (int *)malloc(GL->numVertexes * sizeof(int));
    	for(i=0;i<GL->numVertexes;i++)
    	{
    		ltv[i] = 0;
    	}
    	stack2 = (int *)malloc(GL->numVertexes * sizeof(int));
    	while(0 != top)
    	{
    		gettop = stack[top];
    		top = top - 1;
    		count = count + 1;
    		top2 = top2 + 1;
    		stack2[top2] = gettop;
    		for(e=GL->adjList[gettop].firstedge;e;e=e->next)
    		{
    			k = e->adjvex;
    			if(!(--GL->agjList[k].in))
    			{
    				top = top + 1;
    				stack[top] = k;
    			}
    			/*
    			计算事件发生最晚时间，即走最大路径
    			*/
    			if((ltv[gettop]+e->weight)>ltv[k])
    			{
    				ltv[k] = ltv[gettop] + e->weight;
    			}
    		}
    	}
    	if(count < GL->numVertexes)
    	{
    		return ERROR;
    	}
    	else
    	{
    		return OK;
    	}
    }

以上程序同时记录了一个节点事件发生的最晚时间。

关键路径代码如下：

/*
    求关键路径
    */
    void CriticalPath(GraphAdjList GL)
    {
    	EdgeNode *e;
    	int i,gettop,k,j;
    	int ete,lte;
    
    	TopologicalSort(GL);
    
    	etv = (int *)malloc(GL->numVertexes * sizeof(int));
    	/*
    	用终点（汇点）的最晚发生时间来初始化其他节点的最早发生时间
    	对终点来说，最晚发生时间=最早发生时间
    	*/
    	for(i=0;i<GL->numVertexes;i++)
    	{
    		etv[i] = ltv[GL->numVertexes - 1];
    	}
    	/*
    	按拓补序列逆序计算事件的最早发生时间
    	*/
    	while(0 != top2)
    	{
    		gettop = stack2[top2--];
    		for(e=GL->adjList[gettop].firstedge;e;e=e->next)
    		{
    			/*
    			k此时是与gettop邻接的边的终点
    			*/
    			k = e->adjvex;
    			/*
    			e->weight是从gettop到k这个边的权值
    			最早发生时间=k节点的最早发生时间-耗时最长的权重
    			*/
    			if(etv[k] - e->weight < etv[gettop])
    			{
    				etv[gettop] = etv[k] - e->weight;
    			}
    		}
    	}
    
    	/*
    	ete：活动的最早开工时间
    	lte：活动的最晚开工时间
    	etv：事件的最早发生时间
    	ltv：事件的最晚发生时间
    	*/
    	for(j=0;j<GL->numVertexes;j++)
    	{
    		for(e=GL->adjList[j].firstedge;e;e=e->next)
    		{
    			/*
    			k是边的终点
    			j是边的起点
    			e是指j到k这条边
    			*/
    			k = e->adjvex;
    			/*
    			*/
    			lte = ltv[j];
    			/*
    			活动的最早发生时间=活动终点事件最早发生时间-活动耗时（权重）
    			*/
    			ete = etv[k] - e->weight;
    			/*
    			比较的是活动的最早和最晚时间
    			*/
    			if(ete == lte)
    			{
    				printf("<v%d,v%d> length:%d ",GL->adjList[j].data,GL->adjList[k].data,e->weight);
    			}
    		}
    	}
    }

整个算法并不难理解，重点在四个时间：

ete：活动的最早开工时间  
lte：活动的最晚开工时间  
etv：事件的最早发生时间  
ltv：事件的最晚发生时间

事件的最晚发生时间是从AOE网的起点开始，到达时间所需耗时（权重）最大的值。如下图

![Center][]

事件的最早发生时间是和事件的最晚发生时间逆向计算的。事件的最晚发生时间，是从起点开始，往终点推算；事件的最早发生时间是从AOE网的终点开始，往起点逆向推算。

事件的最早发生时间=后继事件的最晚发生时间-MAX(权重最大的边)，如下图：

![Center 1][]

**PS：对于AOE网的终点来说，事件的最早发生时间 = 事件的最晚发生时间**

活动的最晚发生时间=活动的起点事件的最晚发生时间

活动的最早发生时间=活动的终点事件的最早发生时间 - 活动的耗时（边的权重）

所谓的关键活动就是：活动的最早发生时间 = 活动的最晚发生时间。根本没有选择的余地的。

理清了这四个时间，关键路径算法就没什么了。