关键路径：
- 拓扑排序主要是解决一个工程能否顺序进行的问题，但是有时候还需要解决工程完成需要的最短时间问题。在前面介绍的AOV网的基础上，再介绍一个新的概念。在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称之为AOE网（Activity On Edge NetWork）。把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。
-
下图即为一个AOE网，其中v0为源点，表示一个工程的开始，v9是汇点，表示整个工程的结束，顶点v0,v1,……,v9分别表示事件，弧<v0,v1>,<v0,v2>,……,<v8,v9>都表示一个活动，用a0,a1,……,a12表示，它们的值代表着活动的持续时间。
AOE网 - 某顶点所代表的事件发生后，从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已结束，该顶点所代表的事件才能发生。把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径称为关键路径，在关键路径上的活动叫关键活动，那么如何找出关键路径？。
- 需要找到所有活动的最早开始时间和最晚开始时间，比较后如果两者相等意味着此活动为关键活动，活动间的路径称为关键路径。定义以下几个参数：
1.事件的最早发生时间etv(earliest time of vertex):即顶点vk的最早发生时间；
etv
其中P[k]表示所有到达顶点vk的弧的集合，len<vi,vk>是弧<vi,vk>的权值。
2.事件的最晚发生时间ltv(latest time of vertex):即顶点vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期；
ltv
其中S[k]表示所有到达顶点vk的弧的集合，len<vj,vk>是弧<vj,vk>的权值。
3.活动的最早开工时间ete(earliest time of edge):即弧ak的最早发生时间；
4.活动的最晚开工时间lte(latest time of edge):即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。
可以由1、2求得3、4，然后根据ete[k]是否与lte[k]相等来判断ak是否是关键活动。即ete=etv[k],lte=ltv[j]-len<vk,vj> - 注意，可能存在多条关键路径，则单单提高一条关键路径上的关键活动的速度并不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。
代码示例
使用上一篇中拓扑排序时的邻接表结构，https://www.jianshu.com/p/7e16d412babf
ALGraph.h
//***************关键路径******************
//拓扑排序并计算事件的最早和最晚发生时间
void TopologicalSort_CriticalPath(GraphAdjList G, int etv[], stack<int>& ts);
//求关键路径
void CriticalPath(GraphAdjList ALG, int ltv[], int etv[], stack<int>& ts);
ALGraph.cpp
//***************关键路径******************
//拓扑排序并计算事件的最早和最晚发生时间
void TopologicalSort_CriticalPath(GraphAdjList G, int etv[], stack<int>& ts)
{
stack<int> s; //存放入度为0的顶点,只对该栈中的顶点进行操作
for (int i = 0; i < G.numVertexes; i++)
{
if (G.adjList[i].in == 0)
{
s.push(i);
}
}
int count = 0; //统计输出顶点个数
while (!s.empty()) //栈不为空则继续
{
int x = s.top();
cout << G.adjList[x].data << " "; //输出顶点
count++;
ts.push(x); //保存拓扑序列（当出栈时就成为逆序的拓扑序列）
s.pop(); //出栈然后删除此顶点及对应的边
EdgeNode* e = G.adjList[x].firstEdge; //第一条边
while (e)
{
if (e->weight + etv[x] > etv[e->adjvex])//如果此条边的权重+弧尾顶点的最早时间大于原本弧头顶点的最早时间，则进行更新
{
etv[e->adjvex] = e->weight + etv[x];//更新最早时间
}
if (!(--G.adjList[e->adjvex].in)) //要删除的边对应的顶点入度减一，如果为0，则入栈
{
s.push(e->adjvex);
}
e = e->next;
}
}
if (count != G.numVertexes)
{
cout << "Sort Error" << endl;
}
else
{
cout << "Sort Success" << endl;
}
}
//求关键路径
void CriticalPath(GraphAdjList ALG, int etv[], int ltv[], stack<int>& ts)
{
//step1:拓扑排序得到顶点的最早开始时间etv和拓扑序列ts
TopologicalSort_CriticalPath(ALG, etv, ts);
for (int i = 0; i < ALG.numVertexes; i++)
{
ltv[i] = etv[ALG.numVertexes - 1]; //ltv初始化为最后一个顶点的最早开始时间
}
//step2:计算ltv
while (!ts.empty())
{
int x = ts.top(); //拓扑排序后的逆序
ts.pop();
EdgeNode* e = ALG.adjList[x].firstEdge;
while (e)
{
if (ltv[e->adjvex] - e->weight < ltv[x])
{
ltv[x] = ltv[e->adjvex] - e->weight;
}
e = e->next;
}
}
int ete, lte; //活动的最早开始时间和最晚开始时间
for (int i = 0; i < ALG.numVertexes; i++) //遍历每个顶点的边
{
EdgeNode* te = ALG.adjList[i].firstEdge;
while (te)
{
ete = etv[i];
lte = ltv[te->adjvex] - te->weight;
if (ete == lte) //如果两者相等，则为关键路径
{
cout << i; //输出关键路径
if (i < ALG.numVertexes - 1)
{
cout << "->";
}
if (i == ALG.numVertexes - 2)
{
cout << te->adjvex << endl;
}
}
te = te->next;
}
}
}
main.cpp
#include "ALGraph.h"
#include <iostream>
#include <stack>
using namespace std;
int main(int argc, char** argv)
{
GraphAdjList ALG;
CreateALGraph(ALG); //创建有向无环图
/*
10 13
0 1 2 3 4 5 6 7 8 9
0 1 3
0 2 4
1 3 5
1 4 6
2 3 8
2 5 7
3 4 3
4 6 9
4 7 4
5 7 6
6 9 2
7 8 5
8 9 3
*/
int* etv = new int[ALG.numVertexes]; //每个顶点的最早时间
int* ltv = new int[ALG.numVertexes]; //每个顶点的最晚时间
stack<int> ts; //拓扑序列的逆序
CriticalPath(ALG, etv, ltv, ts);
return 0;
}
