【关键路径问题（Critical Path）——图】

╰+哭是因爲堅強的太久メ 2022-12-21 14:53 114阅读 0赞

### 关键路径问题（Critical Path） ###

*   *  一、基本术语
     *  二、如何求关键路径
     *   *  1、问题分析
         *  2、求关键路径的步骤
     *  三、算法实现
     *   *  1、算法思想
         *  2、算法描述

**AOE网（Activity On Edges）\------用边表示活动的网络  
1、用一个有向图表示一个工程的各子工程及其相互制约的关系，弧表示活动，权表示活动持续的时间，顶点表示事件（活动的开始或结束时间），称这种有向图为边表示活动的网，简称AOE网。  
2、AOE网用来估算工程的完成时间。**

## 一、基本术语 ##

**源点：入度为0的顶点（只有一个）  
汇点：出度为0的顶点（只有一个）  
路径长度：路径上各活动持续时间之和  
整个工程完成的时间：从有向图的源点到汇点的最长路径  
关键路径：路径长度最长的路径**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]

## 二、如何求关键路径 ##

### 1、问题分析 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]

### 2、求关键路径的步骤 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]

## 三、算法实现 ##

### 1、算法思想 ###

**（1）设每个结点的最早发生时间为0，将入度为0的结点进栈  
（2）将栈中入度为0的结点V取出，并压入另一个栈，用于形成逆向拓扑排序的序列  
（3）根据邻接表找到结点V的所有的邻接结点，将结点V的最早发生时间+活动的权值 得到的和同邻接结点的原最早发生时间进行比较；如果该值大，则用该值取代原最早发生时间。另外，将这些邻接结点的入度减一。如果某一结点的入度变为0，则进栈。  
（4）反复执行2、3；直至栈空为止。**

### 2、算法描述 ###

Status CriticalPath(ALGraph G)
    {
        
    	//G为邻接表存储的有向网，输出G的各项关键活动
    	if (!TopologicalOrder(G, topo)) return ERROR;
    	//调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环
    	n = G.vexnum;			//n为顶点的个数
    	for (i = 0;i < n;i++)			//给每个事件的最早发生时间置初值为0
    		ve[i] = 0;
    	/*按照拓扑次序求每个事件的最早发生时间*/
    	for (i = 0;i < n;i++)			//for循环结束才能求得最早发生时间
    	{
        
    		k = topo[i];			//取得拓扑序列中的顶点序号k
    		p = G.vertices[k].firstarc;			//p指向k的第一个邻接点
    		while (p != NULL)			//依次更新k的所有邻接顶点的最早发生时间
    		{
        
    			j = p->adjvex;			//j为邻接顶点的序号
    			if (ve[j] < ve[k] + p->weight)			//更新顶点j的最早发生时间ve[j]
    				ve[j] = ve[k] + p->weight;
    			p = p->nextarc;			//p指向k的下一个邻接顶点
    		}
    	}
    	for (i = 0;i < n;i++)			//给每个事件的最迟发生时间置初值为ve[n-1]
    		vl[i] = ve[n - 1];
    	/*按逆拓扑次序求每个事件的最迟发生时间*/
    	for (i = n - 1;i >= 0;i--)
    	{
        
    		k = topo[i];			//取得拓扑序列中的顶点序号k
    		ArcNode* p = G.vertices[k].firstarc;			//p指向k的第一个邻接顶点
    		while (p != NULL)
    		{
        	//根据k的邻接点，更新k的最迟发生时间
    			j = p->adjvex;			//j为邻接顶点的序号
    			if (vl[k] > vl[j] - p->weight)			//更新顶点k的最迟发生时间vl[k]
    				vl[k] = > vl[j] - p->weight;
    			p = p->nextarc;			//p指向下一个邻接顶点
    		}
    	}
    	/*判断每一活动是否为关键活动*/
    	for (i = 0;i < n;i++)
    	{
         //每次循环针对vi为活动开始点的所有活动
    		p = G.vertices[i].firstarc;			//p指向i的第一个邻接顶点
    		while (p != NULL)
    		{
        
    			j = p->adjvex;			//j为i的邻接顶点的序号
    			e = ve[i];			//计算活动<vi,vj>的最早开始时间
    			l = vl[j] - p->weight;			//计算活动<vi,vj>的最迟开始时间
    			if (e == l)		//若为关键活动，输出<vi,vj>
    				cout << G.vertices[i].data << G.vertices[j].data;
    			p = p->nextarc;			//p指向i的下一个邻接顶点
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/5144f46a9ea9482f809fe397ce2845e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/6258744c513747139b830a722a7e6ddd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/506a49deb9bd404a94954a9c2b88610d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/bb2e511b1c6e4c299a616f8c501900c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/eb7c901a331d431586b3a54988b8e109.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/7db1e6489f184e9fb1b6eec1cfbcdb60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/f88f1c22a3874a18aeb96232881e8569.png