关键路径怎么求？求详解。

关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。

1． 什么是拓扑排序？

举个例子先：一个软件专业的学生学习一系列的课程，其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边表示先决条件。若课程i是课程j的先决条件，则图中有弧<i,j>。若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列，必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前，若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列，称之为拓扑序列。

2． 如何实现拓扑排序？

很简单，两个步骤：

1． 在有向图中选一个没有前驱的顶点且输出。

2． 从图中删除该顶点和以它为尾的弧。

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。

3． 什么是关键路径？

例子开头仍然，图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2，v9，每个事件表示在它之前的活动一完成，在它之后的活动可以开始。如v1表示整个工程的开始，v9表示整个工程结束，v5表示a4和a5已完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天。

由于整个工程只有一个开始点和一个完成点，故在正常情况(无环)下，网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
那么该工程待研究的问题是：1完成整项工程至少需要多少时间？2哪些活动是影响工程进度的关键？
由于在AOE-网中有些活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。
假设开始点是v1，从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候，也即是l(i)=e(i)的活动，我们称其为关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。
因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的功效，缩短整个工期。
4． 如何实现关键路径？
由上面的分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系
e(i) = ve(j)
l(i) = vl(k) - dut(<j,k>)
求解ve(j)和vl(j)需分两个步进行：
1） 从ve(0)=0开始向前推进求得ve(j)
Ve(j) = Max{ve(i) + dut(<i,j>) };<i,j>属于T，j=1,2,n-1
其中T是所有以第j个顶点为头的弧的集合。

2） 从vl(n-1) = ve(n-1)起向后推进求得vl(j)
vl(i) = Min{vl(j) - dut(<i,j>};<i,j>属于S，i=n-2,,0
其中，S是所有以第i个顶点为尾的弧的集合。
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说，ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)必须在Vj的所有后继的最迟发生时间求得之后才能确定。因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。

具体算法描述如下：
1． 输入e条弧<j,k>，建立AOE-网的存储结构。
2． 拓扑排序，并求得ve[]。从源点V0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。
3． 拓扑逆序，求得vl[]。从汇点Vn出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4． 求得关键路径。根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。

为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中，增设一个栈，以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列。

package graph;
import javautil;
public class Grph_CriticalPath 
{
Graph_AdjList adjList;
Stack<Integer> T = new Stack<Integer>(); 
int ve[];
int vl[];
final int max = 10000;

public Grph_CriticalPath(Graph_AdjList adjList)                   //图的存储结构是用的邻接表
{
thisadjList = adjList;
int length = adjListvetexValuelength;
ve = new int[length];
vl = new int[length];
for(int i=0;i<length;i++)
{
ve[i] = 0;
vl[i] = max;
}
}

public void getCriticalPath()
{
topologicalOrder();

int t = Tpop();
Tpush(t);
vl[t] = ve[t];
while(!TisEmpty())
{
int j = Tpop();
for(Graph_AdjListArcNode p = adjListvetex[j]firstArc; p!=null ;p = pnext)
{
int k = padjvex;
if(vl[k]-pweight<vl[j])
{
vl[j] = vl[k]-pweight;
}
}
}
for(int i=0;i<velength;i++)
{
for(Graph_AdjListArcNode p = adjListvetex[i]firstArc; p!=null ;p = pnext)
{
int k = padjvex;
int ee = ve[i];
int el = vl[k]-pweight;
if(ee==el)
{
Systemoutprint(i+","+k+"     ");
}

}
}
}

public void topologicalOrder()
{
Stack<Integer> S = new Stack<Integer>();
Spush(0);
int count = 0;
while(!SisEmpty())
{
int j = Spop();
Tpush(j);
count++;
Graph_AdjListArcNode p = null;
for(p = adjListvetex[j]firstArc; p!=null ;p = pnext)
{
int k = padjvex;
if(--adjListdegree[k]==0)
{
Spush(k);
}
if(ve[j]+pweight>ve[k])
{
ve[k] = ve[j]+pweight;
}
}
}
if(count<adjListvetexValuelength)
{
Systemoutprintln("图中存在环路！");
return;
}
}

public void print()
{
while(!TisEmpty())
{
Systemoutprint(Tpop()+"     ");
}
}

public void printVel()
{
Systemoutprintln();
for(int i=0;i<velength;i++)
{
Systemoutprint(ve[i]+"    ");
}
Systemoutprintln();
for(int i=0;i<vllength;i++)
{
Systemoutprint(vl[i]+"    ");
}
}


}

转自：>

最早开始时间等于当前边起始结点的最早发生时间。最晚开始时间等于当前边指向结点的最迟发生时间-当前边的权值。

最早发生时间和最迟发生时间相同的结点即为关键路径上的节点。例如节点4有两个前驱结点（节点2和3），节点2到节点4的最早发生时间是a1+a3也就是8，节点3到节点4的最早发生时间是a2+a4也就是12，因为12>8，所以节点4的最早发生时间是12。

扩展资料：

理解数据结构注意事项：

有时候队列中还会设置表头结点，就是在队头的前面还有一个结点，这个结点的数据域为空，但是指针域指向队头元素。

Key-HashMap结构，相比String类型将这整个对象持久化成JSON格式，Hash将对象的各个属性存入Map里，可以只读取/更新对象的某些属性。

性表的链式存储方式及以下几种常用链表的特点和运算：单链表，循环链表，双向链表，双向循环链表。单链表的归并算法，循环链表的归并算法，双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。

参考资料来源：百度百科-数据结构

参考资料来源：人民网-历史图上的PageRank算法设计与实现

有向无环图DAG
顶点表示活动的网络AOV网：用DAG图表示一个工程，其顶点表示活动，有向边<vi,vj>表示活动vi必须先于活动vj进行
拓扑排序（由一个有向无环图的顶点组成的序列）
1每个顶点出现且仅出现一次
2若顶点A在序列中排在顶点B之前，则图中不存在B到A的路径
每个DAG图都有一个或多个拓扑排序序列。
若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序序列中，每个顶点有唯一的前驱后继关系，再做拓扑排序时，则排序结果是唯一的。
若邻接矩阵是三角矩阵的话拓扑排序一定存在，反之不一定。
步骤
1从DAG图中选择一个没有前驱的顶点并输出（必须在它之前进行大的活动已经都完成了）
2从图中删除该顶点和所有以它为起点的有向边
3重复1，2直到当前的DAG图为空或当前图中不存在无前驱的结点为止。后者说明有环。

栈

时间复杂度O(|V|+|E|)
用深度优先遍历也可以实现拓扑排序
若已知无环图，则可用拓扑排序来改进Dijkstra算法
以拓扑顺序来选取顶点，运行时间为O(|E|+|V|)

用边表示活动的网络AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，以边上的权值表示完成该活动的开销。
1只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
2只有在进入某一顶点的各有向边所代表的活动都已结束，该顶点所代表的事件才能发生。
仅有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始。仅有一个出度为0的顶点，结束结点（汇点），表示整个工程的结束。
有些活动是可以并行进行的
从源点都汇点的路径可能有多条，所有路径上的活动都完成了整个工程才算结束，所以把路径长度最大的称为 关键路径 ，其上的活动称为 关键活动 。完成整个工程的最短时间就是关键路径的长度。关键活动不能按时完成，则整个工程的完成时间都会受到影响。
事件Vk的最早发生时间Ve(k)
从开始顶点V到Vk的最长路径长度
Ve(V)=0
Ve(k)=Max{Ve(j)+Weight(Vj, Vk)}
从前往后计算
事件Vk的最迟发生时间Vl(k)
在不推迟整个工程完成的前提下，即保证它所指向的时间Vi在Ve(i)时刻能够发生时，该事件最迟必须发生的时间。
Vl(汇点)=Ve(汇点)
Vl(j)=Min{Vl(k)-Weight(Vj, vk)}
从后往前计算
活动Ai的最早开始时间E(i)
等于该活动的起点所表示的事件的最早发生时间
活动Ai的最迟开始时间L(i)
等于该活动的终点所表示的事件的最迟发生时间减去该活动所需要的时间
活动Ai可以拖延的时间D(i)
其最早开始时间与最迟开始时间的差值
若为0的话，就代表该活动必须要如期完成，否则会拖延完成整个工程的进度，则该活动是关键活动。

输入e条弧<j，k>，建立AOE网的存储结构；从源点v1出发，令ve(1)=0，求 ve(j)，2<=j<=n；从汇点vn出发，令vl(n)=ve(n)，求 vl(i)，1<=i<=n-1。

根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

扩展资料

在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。

而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。

关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。

参考资料来源：百度百科-关键路径法

参考资料来源：百度百科-关键路径

---