相关概念
AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网(Activity On Edge Network)。
关键路径与拓扑排序的区别：拓扑排序主要是解决一个工程能否顺利进行的问题，关键路径解决的是工程完成所需要的最短时间问题。换句话说，关键路径问题需要在拓扑排序的基础上得到完成工程的最短时间，因为工程首先必须是可以被完成的，也就是网中不存在环路时，才能进一步讨论工程完成所需的最短时间问题。
AOE网和AOV网：AOV网是顶点表示活动的网，它只描述活动之间的制约关系；AOE网是用边表示活动的网，边上的权值表示活动持续的时间。
关键路径：从源点到汇点具有最大长度的路径称为关键路径，在关键路径上的活动叫关键活动。只有缩短关键路径上的关键活动时间才可以减少整个工期长度。
关键路径算法参数介绍
事件的最早发生时间etv(earliest time of vertex):顶点Vn的最早发生时间;
事件的最晚发生时间ltv(latest tiem of vertex):顶点Vn的最晚发生时间;
活动的最早开工时间ete(earliest time of edge):弧En的最早发生时间;
活动的最晚开工时间lte(latest time of edge):弧En的最晚发生时间，也就是不推迟工期的最晚开工时间。
关键路径算法由etv和ltv求得ete和lte,当ete与lte相等时表示活动没有空闲时间，是关键活动。
etv和ltv数组的计算方法
etv数组计算公式.png
P[k]表示所有到达顶点Vk的弧的集合，即Vk是弧的终点。
ltv数组计算公式.png
S[k]表示所有从顶点Vk出发的弧的集合，即Vk是弧的起点。
源代码
带权有向图采用邻接表的数据结构表示
顶点表结点类
/**
* 顶点表结点类
*
* @author Shaw
*
*/
class VertexNode {
// 顶点入度
private int in;
// 顶点域
private String data;
// 指向边表
private EdgeNode firstEdge;
public VertexNode(int in, String data, EdgeNode firstEdge) {
super();
this.in = in;
this.data = data;
this.firstEdge = firstEdge;
}
public int getIn() {
return in;
}
public void setIn(int in) {
this.in = in;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public EdgeNode getFirstEdge() {
return firstEdge;
}
public void setFirstEdge(EdgeNode firstEdge) {
this.firstEdge = firstEdge;
}
}
边表顶点类
/**
* 边表顶点类
* @author Shaw
*
*/
class EdgeNode {
//邻接点域，存储该顶点对应的下标
private int adjvex;
//权值域
private int weight;
//指向下一个邻接点
private EdgeNode next;
public EdgeNode(int adjvex, int weight, EdgeNode next) {
super();
this.adjvex = adjvex;
this.weight = weight;
this.next = next;
}
public int getAdjvex() {
return adjvex;
}
public void setAdjvex(int adjvex) {
this.adjvex = adjvex;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public EdgeNode getNext() {
return next;
}
public void setNext(EdgeNode next) {
this.next = next;
}
}
关键路径算法核心类
/**
* 关键路径算法
*
* @author Shaw
*
*/
class CriticalPath {
private List<VertexNode> verList;
private int[] etv; // (earliest time of edge)事件最早发生时间数组
private int[] ltv; // (latest time of edge)事件最迟发生时间数组
private Stack<Integer> stack2; // 用于存放拓扑排序结果的栈
// 建图
public void buildAoeGraph() {
VertexNode v0 = new VertexNode(0, "v0", null);
EdgeNode v0e1 = new EdgeNode(2, 4, null);
EdgeNode v0e2 = new EdgeNode(1, 3, null);
v0.setFirstEdge(v0e1);
v0e1.setNext(v0e2);
VertexNode v1 = new VertexNode(0, "v1", null);
EdgeNode v1e1 = new EdgeNode(4, 6, null);
EdgeNode v1e2 = new EdgeNode(3, 5, null);
v1.setFirstEdge(v1e1);
v1e1.setNext(v1e2);
VertexNode v2 = new VertexNode(0, "v2", null);
EdgeNode v2e1 = new EdgeNode(5, 7, null);
EdgeNode v2e2 = new EdgeNode(3, 8, null);
v2.setFirstEdge(v2e1);
v2e1.setNext(v2e2);
VertexNode v3 = new VertexNode(0, "v3", null);
EdgeNode v3e1 = new EdgeNode(4, 3, null);
v3.setFirstEdge(v3e1);
VertexNode v4 = new VertexNode(0, "v4", null);
EdgeNode v4e1 = new EdgeNode(7, 4, null);
EdgeNode v4e2 = new EdgeNode(6, 9, null);
v4.setFirstEdge(v4e1);
v4e1.setNext(v4e2);
VertexNode v5 = new VertexNode(0, "v5", null);
EdgeNode v5e1 = new EdgeNode(7, 6, null);
v5.setFirstEdge(v5e1);
VertexNode v6 = new VertexNode(0, "v6", null);
EdgeNode v6e1 = new EdgeNode(9, 2, null);
v6.setFirstEdge(v6e1);
VertexNode v7 = new VertexNode(0, "v7", null);
EdgeNode v7e1 = new EdgeNode(8, 5, null);
v7.setFirstEdge(v7e1);
VertexNode v8 = new VertexNode(0, "v8", null);
EdgeNode v8e1 = new EdgeNode(9, 3, null);
v8.setFirstEdge(v8e1);
VertexNode v9 = new VertexNode(0, "v9", null);
verList = new ArrayList<>();
verList.add(v0);
verList.add(v1);
verList.add(v2);
verList.add(v3);
verList.add(v4);
verList.add(v5);
verList.add(v6);
verList.add(v7);
verList.add(v8);
verList.add(v9);
}
// 拓扑排序，用于关键路径的计算
// 求出事件的最早发生时间数组etv[]
public void topologicalSortForCriticalPath() {
Stack<Integer> stack = new Stack<>();
etv = new int[verList.size()];
stack2 = new Stack<>();
int count = 0;
// 初始化所有顶点表结点的入度值
for (int i = 0; i < verList.size(); i++) {
// 初始化etv数组
etv[i] = 0;
EdgeNode edgeNode = verList.get(i).getFirstEdge();
while (edgeNode != null) {
// 边集表中出现的下标(adjvex)所对应的顶点入度加1
VertexNode vertexNode = verList.get(edgeNode.getAdjvex());
vertexNode.setIn(vertexNode.getIn() + 1);
edgeNode = edgeNode.getNext();
}
}
// 将所有入度为0的顶点入栈
for (int i = 0; i < verList.size(); i++) {
if (verList.get(i).getIn() == 0) {
stack.push(i);
}
}
while (!stack.isEmpty()) {
// 从栈中弹出一个入度为0的顶点
int vertex = stack.pop();
// 将出栈的顶点压入stack2栈中用于关键路径算法
stack2.push(vertex);
count++;
// 获取弹出的顶点指向的第一个边结点
EdgeNode edgeNode = verList.get(vertex).getFirstEdge();
while (edgeNode != null) {
// 获取边表结点的Adjvex值，该值存储对应顶点表结点的下标值
int adjvex = edgeNode.getAdjvex();
// 获取边表结点指向的顶点表结点
VertexNode vertexNode = verList.get(adjvex);
// 删除边结点，也就是将对应的顶点表结点的入度减1
vertexNode.setIn(vertexNode.getIn() - 1);
// 如果该顶点表结点入度为0时压栈
if (vertexNode.getIn() == 0) {
stack.push(adjvex);
}
// 求各顶点事件的最早发生时间值
if ((etv[vertex] + edgeNode.getWeight()) > etv[adjvex]) {
etv[adjvex] = etv[vertex] + edgeNode.getWeight();
}
// 获取下一个边表结点的值
edgeNode = edgeNode.getNext();
}
}
}
// 关键路径算法
public void CriticalPath() {
EdgeNode edgeNode;
int i, stacktop, k, j;
// 活动最早发生时间和最迟发生时间
int ete, lte;
topologicalSortForCriticalPath();
System.out.println("etv数组：");
for (i = 0; i < verList.size(); i++) {
System.out.print(etv[i] + " ");
}
// 事件最晚发生时间
ltv = new int[verList.size()];
// 初始化ltv数组
for (i = 0; i < verList.size(); i++) {
ltv[i] = etv[verList.size() - 1];
}
// while循环计算具体的ltv数组的值
while (!stack2.isEmpty()) {
//从拓扑排序的结果从后往前遍历，因为先是从栈1中弹出后在压入栈2的，所以栈2的顶是拓扑排序的最后一个结果
stacktop = stack2.pop();
edgeNode = verList.get(stacktop).getFirstEdge();
while (edgeNode != null) {
k = edgeNode.getAdjvex();
if (ltv[k] - edgeNode.getWeight() < ltv[stacktop]) {
ltv[stacktop] = ltv[k] - edgeNode.getWeight();
}
edgeNode = edgeNode.getNext();
}
}
System.out.println("\nltv数组：");
for (i = 0; i < verList.size(); i++) {
System.out.print(ltv[i] + " ");
}
System.out.println("\n关键路径：");
for (j = 0; j < verList.size(); j++) {
edgeNode = verList.get(j).getFirstEdge();
while (edgeNode != null) {
k = edgeNode.getAdjvex();
ete = etv[j];
lte = ltv[k] - edgeNode.getWeight();
if (ete == lte) {
System.out.println("<"+verList.get(j).getData()+","+verList.get(k).getData()+"> weight : "+edgeNode.getWeight());
}
edgeNode = edgeNode.getNext();
}
}
}
}
测试图以及邻接表
有向带权无换图.png
邻接表图.png
测试程序
public class CriticalPathMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
CriticalPath criticalPath = new CriticalPath();
criticalPath.buildAoeGraph();
criticalPath.CriticalPath();
}
}
测试结果
关键路径算法结果图.png
