来源：网友投稿 浏览数：8266 关注：239人
大家好，近很多小伙伴在关注关键路径怎么求，以下是(www.liyan0123)小编整理的与关键路径怎么求相关的内容分享给大家，一起来看看吧。
本文目录一览：
关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。
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 pat )。
假设开始点是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 grap ;
import java.util.*;
public class Grp _CriticalPat
{
Grap _AdjList adjList;
StackInteger T = new StackInteger();
int ve[];
int vl[];
final int max = 10000;
public Grp _CriticalPat (Grap _AdjList adjList) //图的存储结构是用的邻接表
{
t is.adjList = adjList;
int lengt = adjList.vetexValue.lengt ;
ve = new int[lengt ];
vl = new int[lengt ];
for(int i=0;ilengt ;i++)
{
ve[i] = 0;
vl[i] = max;
}
}
public void getCriticalPat ()
{
topologicalOrder();
int t = T.pop();
T.pus (t);
vl[t] = ve[t];
w ile(!T.isEmpty())
{
int j = T.pop();
for(Grap _AdjList.ArcNode p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(vl[k]-p.weig tvl[j])
{
vl[j] = vl[k]-p.weig t;
}
}
}
for(int i=0;ive.lengt ;i++)
{
for(Grap _AdjList.ArcNode p = adjList.vetex[i].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
int ee = ve[i];
int el = vl[k]-p.weig t;
if(ee==el)
{
System.out.print(i+","+k+" ");
}
}
}
}
public void topologicalOrder()
{
StackInteger S = new StackInteger();
S.pus (0);
int count = 0;
w ile(!S.isEmpty())
{
int j = S.pop();
T.pus (j);
count++;
Grap _AdjList.ArcNode p = null;
for(p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(--adjList.degree[k]==0)
{
S.pus (k);
}
if(ve[j]+p.weig tve[k])
{
ve[k] = ve[j]+p.weig t;
}
}
}
if(countadjList.vetexValue.lengt )
{
System.out.println("图中存在环路！");
return;
}
}
public void print()
{
w ile(!T.isEmpty())
{
System.out.print(T.pop()+" ");
}
}
public void printVel()
{
System.out.println();
for(int i=0;ive.lengt ;i++)
{
System.out.print(ve[i]+" ");
}
System.out.println();
for(int i=0;ivl.lengt ;i++)
{
System.out.print(vl[i]+" ");
}
}
}
转自：
输入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)的为关键活动。
求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
扩展资料
在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。
而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。
关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。
参考资料来源：百度百科-关键路径法
参考资料来源：百度百科-关键路径
以上就是关键路径怎么求的相关介绍，希望能对大家有所帮助。
获赞：429 | 收藏：86 | 发布时间：2024-05-21 00:31:15
原文链接：http://www.liyan0123.com/54237.html
=========================================
特别声明：以上内容来源于网友投稿，编辑整理发布，如有不妥之处，请与我方联系删除处理。