【数据结构】什么的图的关键路径？关键路径相关概念？关键路径算法实现？

朴灿烈づ我的快乐病毒、 2023-09-26 10:28 25阅读 0赞

## **目录** ##

一、什么是关键路径？

1、现实问题

二、关键路径相关概念？

三、关键路径算法实现？

1、算法分析

2、算法步骤

3、算法实现

--------------------

## 一、什么是关键路径？ ##

> 关键路径：若有向图中，各顶点表示事件，各有向边表示活动持续事件，则该图为活动边网络，简称AOE网。AOE网中的关键路径，**就是完成整个网络所需的最短时间**，**亦最长路径**，AOE网中，往往有若干项活动可以平行的进行，因此，**从开始顶点到最后一个顶点的最长路径称为关键路径。**

![569085ba95654997a372e93332a13d18.png][]

#### 1、现实问题 ####

**问题：**

*  假设以有向图表示一个施工流图，弧上的权值表示完成该项子工程所需时间。
 *  问：**整个工程完成的最短时间？以及哪些活动将是影响整个工程如期完成的关键所在？**

**使用图描述上面情况：**

*  弧表示活动
 *  弧上的数字表示完成该项活动所需的时间。

![32855a7a47344687b0e1391571dc2acc.png][]

--------------------

## 二、关键路径相关概念？ ##

**1、AOE(Activity On Edge)网：**若以**弧表示活动**，弧上的**权值**表示进行该项活动所需的**时间**，以**顶点表示事件**Event，称这种有向网为==**边活动网络**==，简称为AOE。

**2、事件：**是一个关于某几项活动开始或完成的断言。

>  *  指向它的弧表示的活动已经完成。
>  *  而从它出发的弧表示的活动开始进行
>  *  整个有向图也表示了活动之间的优先关系
>  *  这样的有向网也是**不允许存在环的**

![e1a5ea6c9f4a480e91642230c8dd2e47.png][]

**3、源点和汇点：**

>  *  源点：表示工程**开始事件的顶点的入度为零**。
>  *  汇点：表示工程结束事件的顶点的**出度为零**。
>  *  一个工程AOE网应该是**只有一个源点和一个汇点的有向无环图**

**4、关键路径和关键活动：**

>  *  关键路径：由于AOE网中**某些活动可以并行进行**，故完成整个工程的最短时间即为从源点到汇点==**最长路径的长度**==，这个路径称为关键路径。
>  *  关键活动：构成关键路径的**弧**即为关键活动。
>  *  实例：下图工程从开始到完成需要18天
>     
>      *  a1、a4、a8和a11四项活动必须按时开始并按时完成，否则将延误整个工程的工期，使整个工程不能在18天内完成。
>      *  于是，**称a1、a4、a8和a11为AOE图的关键活动**。
>      *  **由a1、a4、a8和a11构成的路径称为关键路径。**

![5c98084698d64b169229ce7fe722ee02.png][]

## 三、关键路径算法实现？ ##

#### 1、算法分析 ####

*  相关概念
    
    >  *  假设顶点v0为源点，vn-1 为汇点
    >  *  时间v0的发生时刻为0时刻
    >  *  从v0到vi的最长路径叫做事件vi的最早发生时间
    >  *  用e(i)表示==活动的最早开始时间==。（这个时间决定了所有以vi为尾的弧所表示活动的最早开始时间）
    >  *  用l(i)表示==活动的最晚开始时间==。
    >  *  两者之差l(i)-e(i)意味着完成活动ai的时间余量
    >  *  当l(i)=e(i)时的活动成为==关键活动==。
    >  *  用ve(j)表示==事件vj的最早开始时间==。
    >  *  用vl(j)表示==事件vj的最晚开始时间==。
 *  关键路径和非关键路径分析

![668426c4ae00446bb9afad474ed3cb1e.png][]

*  顶点v0到v8的一条关键路径是：(v0, v1, v4, v6, v8) ，路径长度为18。
 *  **活动a6不是关键活动**，它的最早开始时间为5，最晚开始时间为8，时间余量为3。也就是说a6延迟3天，并不会影响整个工程的完成。

![588942030a0f440fb594653196709bf9.png][]

*  总结：
    
    > 1.要缩短整个工程，必须先找到关键路径，提高关键活动的工效。
    > 
    > 2.由于关键路径上的活动都是关键活动，所以，**提前完成非关键活动并不能加快工程的进度。**

#### 2、算法步骤 ####

1、从源点v0触发，令ve(0) = 0，按拓扑有序序列求其余各顶点的ve(j)=maxi \{ve(i) + |vi, vj| \} , <vi, vj> ∈ T，其中：T是所有以vj为头的弧的集合。若得到的拓扑有序序列中**顶点的个数小于网中的顶点个数n**，则说明网中有环，不能求出关键路径，算法结束。

![2d6d18263c7f47c5b0e352c267a0644c.png][]

2、从汇点vn-1出发，令vl(n-1) = ve(n-1) ，按逆拓扑有序序列求其余各顶点的 vl(i)=minj \{vl(j) - |vi, vj| \} , <vi, vj> ∈ S，其中：S是所有以vj为尾的弧的集合。

![0754a4e238ff41a88feec9b9f71767e2.png][]

3、求每一项活动ai（1<=i<=n）的**最早开始时间e(i)=ve(j)**，vj是ai的起点。

![d8ed1f26944741faaadd928aaf6857b7.png][]

4、求每一项活动ai的最晚开始时间l(i) = vl(j) - |vi, vj| , vi是ai的起点， vj是ai的终点。

![e9b24648b1894d0a963be0b836304224.png][]

5、若对于满足e(i) = l (i) ，则它是关键活动

![d4dcf341f4e44192a6fc4780d5020ae4.png][]

两条关键路径：

![ed7af04427f04330abd90adf116aa929.png][]

--------------------

#### 3、算法实现 ####

public class CriticalPath {
    	private LinkStack T = new LinkStack();	// 拓扑逆序列顶点栈
    
    	private int[] ve, vl;					// 各顶点的最早发生时间和最迟发生时间
    
    	// 有向图G采用邻接表存储，求各顶点的最早发生时间ve，若G无回路，则用栈T返回G的一个拓扑序列，且函数返回true，否则为false
    	public boolean topologicalOrder(ALGraph G) throws Exception {
    		int count = 0;										// 输出顶点计数
    		int[] indegree = TopologicalSort.findInDegree(G);	// 求各个顶点的入度
    		LinkStack S = new LinkStack();						// 建零入度顶点栈S
    		for (int i = 0; i < G.getVexNum(); i++)
    			if (indegree[i] == 0)							// 入度为0者进展
    				S.push(i);
    		ve = new int[G.getVexNum()];						// 初始化
    		while (!S.isEmpty()) {
    			int j = (Integer) S.pop();
    			T.push(j);										// j号顶点入T栈并计数
    			++count;
    			for (ArcNode arc = G.getVexs()[j].firstArc; arc != null; arc = arc.nextArc) {
    				int k = arc.adjVex;
    				if (--indegree[k] == 0)						// 对j号顶点的每个邻接点的入度减1
    					S.push(k);								// 若入度减为0，则入栈
    				if (ve[j] + arc.value > ve[k])
    					ve[k] = ve[j] + arc.value;
    			}
    		}
    
    		if (count < G.getVexNum())
    			return false;									// 该有向图有回路
    		else
    			return true;
    	}
    
    	// G为有向图，输出G的各项关键活动
    	public boolean criticalPath(ALGraph G) throws Exception {
    		if (!topologicalOrder(G))
    			return false;
    		vl = new int[G.getVexNum()];
    		for (int i = 0; i < G.getVexNum(); i++)
    			// 初始化顶点时间的最迟发生时间
    			vl[i] = ve[G.getVexNum() - 1];
    		while (!T.isEmpty()) {					// 按拓扑逆序列求各顶点的vl值
    			int j = (Integer) T.pop();
    			for (ArcNode arc = G.getVexs()[j].firstArc; arc != null; arc = arc.nextArc) {
    				int k = arc.adjVex;
    				int value = arc.value;
    				if (vl[k] - value < vl[j])
    					vl[j] = vl[k] - value;
    			}
    		}
    
    		System.out.println("ve:事件最早发生时间、vl事件最晚发生时间");
    		System.out.println("事件ve\tvl");
    		for (int j = 0; j < G.getVexNum(); j++) {
    			int ee = ve[j];
    			int el = vl[j];
    			System.out.println(G.getVex(j) + "\t" + ee + "\t" + el);		// 输出关键事件
    		}
    		System.out.println("e:活动最早开始时间、l：活动最晚开始时间");
    		System.out.println("源点-->\t汇点权值\te\tl\tl-e\t关键活动");
    		for (int j = 0; j < G.getVexNum(); j++)
    			// 求ee，el和关键活动
    			for (ArcNode arc = G.getVexs()[j].firstArc; arc != null; arc = arc.nextArc) {
    				int k = arc.adjVex;
    				int value = arc.value;
    				int ee = ve[j];
    				int el = vl[k] - value;
    				char tag = (ee == el) ? '*' : ' ';
    				System.out.println(G.getVex(j) + "\t->\t" + G.getVex(k) + "\t"
    						+ value + "\t" + ee + "\t" + el + "\t" + (el-ee) + "\t" + tag);		// 输出关键活动
    			}
    		return true;
    	}
    
    	public static void main(String[] args) throws Exception {
    		ALGraph G = GenerateGraph.generateALGraph();
    		CriticalPath p = new CriticalPath();
    		p.criticalPath(G);
    
    	}
    }
    
    // 调试结果：
    //ve:事件最早发生时间、vl事件最晚发生时间
    //事件  ve	vl
    //v0	0	0
    //v1	6	6
    //v2	4	6
    //v3	5	8
    //v4	7	7
    //v5	7	10
    //v6	16	16
    //v7	14	14
    //v8	18	18
    //e:活动最早开始时间、l：活动最晚开始时间
    //源点-->	汇点  权值	e	l	l-e	关键活动
    //v0	->	v3	5	0	3	3
    //v0	->	v2	4	0	2	2
    //v0	->	v1	6	0	0	0	*
    //v1	->	v4	1	6	6	0	*
    //v2	->	v4	1	4	6	2
    //v3	->	v5	2	5	8	3
    //v4	->	v7	7	7	7	0	*
    //v4	->	v6	9	7	7	0	*
    //v5	->	v7	4	7	10	3
    //v6	->	v8	2	16	16	0	*
    //v7	->	v8	4	14	14	0	*

[569085ba95654997a372e93332a13d18.png]: https://img-blog.csdnimg.cn/569085ba95654997a372e93332a13d18.png
[32855a7a47344687b0e1391571dc2acc.png]: https://img-blog.csdnimg.cn/32855a7a47344687b0e1391571dc2acc.png
[e1a5ea6c9f4a480e91642230c8dd2e47.png]: https://img-blog.csdnimg.cn/e1a5ea6c9f4a480e91642230c8dd2e47.png
[5c98084698d64b169229ce7fe722ee02.png]: https://img-blog.csdnimg.cn/5c98084698d64b169229ce7fe722ee02.png
[668426c4ae00446bb9afad474ed3cb1e.png]: https://img-blog.csdnimg.cn/668426c4ae00446bb9afad474ed3cb1e.png
[588942030a0f440fb594653196709bf9.png]: https://img-blog.csdnimg.cn/588942030a0f440fb594653196709bf9.png
[2d6d18263c7f47c5b0e352c267a0644c.png]: https://img-blog.csdnimg.cn/2d6d18263c7f47c5b0e352c267a0644c.png
[0754a4e238ff41a88feec9b9f71767e2.png]: https://img-blog.csdnimg.cn/0754a4e238ff41a88feec9b9f71767e2.png
[d8ed1f26944741faaadd928aaf6857b7.png]: https://img-blog.csdnimg.cn/d8ed1f26944741faaadd928aaf6857b7.png
[e9b24648b1894d0a963be0b836304224.png]: https://img-blog.csdnimg.cn/e9b24648b1894d0a963be0b836304224.png
[d4dcf341f4e44192a6fc4780d5020ae4.png]: https://img-blog.csdnimg.cn/d4dcf341f4e44192a6fc4780d5020ae4.png
[ed7af04427f04330abd90adf116aa929.png]: https://img-blog.csdnimg.cn/ed7af04427f04330abd90adf116aa929.png