目录
一、什么是关键路径？
关键路径：若有向图中，各顶点表示事件，各有向边表示活动持续事件，则该图为活动边网络，简称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 *