关键路径JS实现

迷南。 2022-03-29 09:52 199阅读 0赞

我勒个去，毕业论文终于提交了，赶紧完成图基本算法的最后一节。。。

## 1 定义 ##

在一个表示工程的带权有向图中，用**顶点表示事件**，用**有向边表示活动**，用**边上的权值表示活动的持续时间**，这种有向图的边表示活动的网，称为**AOE网**。AOE网中没有入边的顶点称为**始点或源点**，没有出边的顶点称为**终点或汇点**。由于一个工程通常总有一个开始和一个结束，因此AOE网只有一个源点和汇点。

与AOV网区别在于，AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动持续的时间。其是建立在活动之间制约关系没有矛盾的基础之上，再来分析整个工程需要多少时间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫**关键路径**，在关键路径上的活动叫**关键活动**。只有找出AOE网中的关键路径，并缩短路径上关键活动的工作时间，才能最有效的缩短完成工程的时间。

## 2 建立测试网 ##

![在这里插入图片描述][20190109101652877.png]  
按照[拓扑排序][Link 1]的邻接表结构，建立测试网：

class vex{ 
    	constructor(value){ 
    		this.data = value;
    		this.firstEdge = null;
    		this.in = 0;   //用于存放顶点的入度
    	}
    
    }
    
    class adjvex{ 
    	constructor(node,weight){ 
    		this.node = node;
    		this.weight = weight;
    		this.next = null;
    	}
    }
    
    class Graph{ 
    	constructor(v,vr){ 
    		let len = v.length;
    		let vexs = new Array(len);
    		let v1=0,v2=0;
    		let newvex = null;
    		for (let i=0;i<len;i++){ 
    			vexs[i] = new vex(v[i]);
    		}
    		for (let arc of vr){ 
    			v1 = v.indexOf(arc[0]);
    			v2 = v.indexOf(arc[1]);
    
    			newvex = new adjvex(v2,arc[2]);
    			newvex.next = vexs[v1].firstEdge;   //头插法
    			vexs[v1].firstEdge = newvex;
    			vexs[v2].in++;
    		}
    		this.adjList = vexs;
    	}
    }
    
    let a = new Graph(['v0','v1','v2','v3','v4','v5','v6','v7','v8','v9','v10','v11','v12','v13'],[['v0','v11',1],['v0','v4',1],['v0','v5',1],['v1','v4',1],['v1','v8',1],['v1','v2',1],['v2','v5',1],['v2','v6',1],['v3','v2',1],['v3','v13',1],['v4','v7',1],['v5','v8',1],['v5','v12',1],['v6','v5',1],['v8','v7',1],['v9','v11',1],['v9','v10',1],['v10','v13',1],['v12','v9',1]]);
    console.log(a);

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

## 3 算法思路 ##

在AOE网中找到关键路径在于如何找到关键活动。对此我们定义几个参数：

*  **事件的最早发生时间etv**：即顶点代表的事件最早发生的时间
 *  **事件的最晚发生时间ltv**：即顶点代表的事件最晚发生的时间
 *  **活动最早的开工时间ete**：即弧代表的活动最早发生时间
 *  **活动最晚的开工时间lte**：即弧代表的活动最晚发生时间，也就是不推迟工期的最晚开工时间。

例如下图，有4个事件： v0，v1，v2和v3，以及4个活动：a0，a1，a2和a4。事件v3必须等到活动a2和a4完成以后才能触发，因此在不推迟工期的条件下，事件v3的最早发生时间和最晚发生时间都是12，且v2的最早和最晚发生时间也都是4，但是对于事件v1，其只要保证在时间7之前发生即可，因此其最早发生时间是3，而最晚发生时间是7。综上所述，要减少整个工程的时间，对于缩减活动a0和a2的时间并没有什么作用，关键要缩减经过事件顶点v2的活动a1和a4的时间。因此经过顶点v2的路径才是关键路径。由此我们可以看出，**一个活动是否为关键活动在于活动最早的开工时间ete是否等于活动最晚的开工时间lte**，若等于，该活动则为关键活动，否则则不是。  
![在这里插入图片描述][20190109110944382.png]  
**在关键路径算法，我们先求得顶点事件的最早和最晚发生时间，再求得弧活动的最早和最晚开工时间，最后比较弧活动的两者时间是否相等，判断是否为关键活动。**

## 4 代码 ##

**整个求解关键路径过程可划分为三部分：**

*  求解各顶点事件的最早发生时间
 *  求解各顶点事件的最晚发生时间
 *  求解各弧上活动的最早和最晚发生时间，并做关键活动的判断

**首先求得各顶点事件的最早发生时间**，可以看到代码与拓扑排序很相似。求各顶点的最早发生时间判定条件如下  
![在这里插入图片描述][20190109143407267.png]  
例如下图，etv\[1\] + a2 ＜ etv\[2\] + a4，所以etv\[3\] = 12。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]

接着根据各顶点事件的最早发生时间，**反向求各顶点的最晚发生时间**，相当于把拓扑排序倒过来，判定条件如下  
![在这里插入图片描述][20190109143953787.png]  
例如下图，顶点v6的最晚发生时间为25，而顶点v7为19，ltv\[6\] - 9 > ltv\[7\] -4，为了保证工程不延期，因此顶点v4最晚发生时间ltv\[4\] = 15  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]

**最后即可根据各顶点事件的最早和最晚发生时间，计算弧上活动的最早和最晚时间，并作比较判断是否为关键活动**。注意的是，弧上活动`<vi,vj>`的最早开工时间不可能早于顶点`vi`事件最早发生时间，而最晚开工时间则不可能晚于顶点`vj`事件最晚发生时间 - 弧上活动持续时间。因此代码如下：

![在这里插入图片描述][20190109160359709.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70]: /images/20220329/7d867a479ef84957b2a6f0dc946ad9a9.png
[20190109101652877.png]: /images/20220329/2f52523de49e4c498899309b8f8cd631.png
[Link 1]: https://blog.csdn.net/zjw_python/article/details/85233809
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 1]: /images/20220329/a3dd2b02fac24e01b33d0caefd55ed29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 2]: /images/20220329/c4a95aeb42b5497283eb666fe368c876.png
[20190109110944382.png]: /images/20220329/ab459b8e82f142a18a8267dfd56291c8.png
[20190109143407267.png]: /images/20220329/ce97075cdfae4c8f85c99185101d18a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 3]: /images/20220329/2c59c6c5ee6045008e3aa55cb98fcff0.png
[20190109143953787.png]: /images/20220329/5d04172c57f04eb1b55b647f63a89d27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqd19weXRob24_size_16_color_FFFFFF_t_70 4]: /images/20220329/1312c77030ec40b993ba4df5ab65ac7c.png
[20190109160359709.png]: /images/20220329/5d956f845232422a83d03ab414c2fc33.png