一、什么是关键路径？
关键路径：若有向图中，各顶点表示事件，各有向边表示活动持续事件，则该图为活动边网络，简称AOE网。AOE网中的关键路径，就是完成整个网络所需的最短时间，亦最长路径，AOE网中，往往有若干项活动可以平行的进行，因此，从开始顶点到最后一个顶点的最长路径称为关键路径。
1、现实问题
问题：
假设以有向图表示一个施工流图，弧上的权值表示完成该项子工程所需时间。
问：整个工程完成的最短时间？以及哪些活动将是影响整个工程如期完成的关键所在？
使用图描述上面情况：
弧表示活动
弧上的数字表示完成该项活动所需的时间。
二、关键路径相关概念？
1、AOE(Activity On Edge)网：若以弧表示活动，弧上的权值表示进行该项活动所需的时间，以顶点表示事件Event，称这种有向网为==边活动网络==，简称为AOE。
2、事件：是一个关于某几项活动开始或完成的断言。
指向它的弧表示的活动已经完成。
而从它出发的弧表示的活动开始进行
整个有向图也表示了活动之间的优先关系
这样的有向网也是不允许存在环的
3、源点和汇点：
源点：表示工程开始事件的顶点的入度为零。
汇点：表示工程结束事件的顶点的出度为零。
一个工程AOE网应该是只有一个源点和一个汇点的有向无环图
4、关键路径和关键活动：
关键路径：由于AOE网中某些活动可以并行进行，故完成整个工程的最短时间即为从源点到汇点==最长路径的长度==，这个路径称为关键路径。
关键活动：构成关键路径的弧即为关键活动。
实例：下图工程从开始到完成需要18天
a1、a4、a8和a11四项活动必须按时开始并按时完成，否则将延误整个工程的工期，使整个工程不能在18天内完成。
于是，称a1、a4、a8和a11为AOE图的关键活动。
由a1、a4、a8和a11构成的路径称为关键路径。
三、关键路径算法实现？
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的最晚开始时间==。
关键路径和非关键路径分析
顶点v0到v8的一条关键路径是：(v0, v1, v4, v6, v8) ，路径长度为18。
活动a6不是关键活动，它的最早开始时间为5，最晚开始时间为8，时间余量为3。也就是说a6延迟3天，并不会影响整个工程的完成。
总结：
1.要缩短整个工程，必须先找到关键路径，提高关键活动的工效。
2.由于关键路径上的活动都是关键活动，所以，提前完成非关键活动并不能加快工程的进度。
2、算法步骤
1、从源点v0触发，令ve(0) = 0，按拓扑有序序列求其余各顶点的ve(j)=maxi {ve(i) + |vi, vj| } , <vi, vj> ∈ T，其中：T是所有以vj为头的弧的集合。若得到的拓扑有序序列中顶点的个数小于网中的顶点个数n，则说明网中有环，不能求出关键路径，算法结束。
2、从汇点vn-1出发，令vl(n-1) = ve(n-1) ，按逆拓扑有序序列求其余各顶点的 vl(i)=minj {vl(j) - |vi, vj| } , <vi, vj> ∈ S，其中：S是所有以vj为尾的弧的集合。
3、求每一项活动ai（1<=i<=n）的最早开始时间e(i)=ve(j)，vj是ai的起点。
4、求每一项活动ai的最晚开始时间l(i) = vl(j) - |vi, vj| , vi是ai的起点， vj是ai的终点。
5、若对于满足e(i) = l (i) ，则它是关键活动
两条关键路径：
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 *
