关键路径的探寻
发布网友
发布时间：2022-04-23 06:01
共1个回答
热心网友
时间：2023-10-17 23:31
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。2） 可以采取如下步骤求得关键活动：
A、从开始顶点 v 1 出发，令 ve（1）=0，按拓扑有序序列求其余各顶点的可能最早发生时间。
Ve(k)=max{ve(j)+t(<j,k>)} （ 1.1 ） j ∈ T 其中T是以顶点vk为尾的所有弧的头顶点的集合（2 ≤ k ≤ n）。
如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。B、从完成顶点 v n 出发，令vl(n)=ve(n），按逆拓朴有序求其余各顶点的允许的最晚发生时间：
vl(j)=min{vl(k)-t(<j,k>)} k ∈ S 其中 S 是以顶点vj是头的所有弧的尾顶点集合（1 ≤ j ≤ n-1）。
C、求每一项活动ai（1 ≤ i ≤ m）的最早开始时间e(i)=ve(j）；最晚开始时间：
l(i)=vl(k)-t(<j,k>) 若某条弧满足 e(i)=l(i) ，则它是关键活动。
对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1,a4,a7,a8,a10,a11 是关键活动。 （1） 完成整个工程至少需要多少时间；
（2） 哪些活动是影响工程的关键。
1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。 （1） 关键路径：从源点到汇点的路径长度最长的路径叫关键路径。
（2） 活动开始的最早时间e(i)
（3） 活动开始的最晚时间l(i) 定义e(i)=l(i）的活动叫关键活动。
（4） 事件开始的最早时间ve(i)
（5） 事件开始的最晚时间vl(i)
设活动ai由弧<j,k>；（即从顶点j到k）表示，其持续时间记为t(<j,k>；），则
e(i)=ve(j)
l(i)=vl(k)-t(<j,k>) （6_6_1）
求ve(i）和vl(j）分两步：
· 从ve（1）=0开始向前递推
ve(j)=Max{ ve(i)+t(<i,j>) } （6_6_2）
<i,j>T,2<=j<=n
其中，T是所有以j为弧头的弧的集合。
· 从vl(n)=ve(n）开始向后递推
vl(i)=Min{ vl(j)-t(<i,j>) } （6_6_3）
<i,j>S,1<=i<=n-1
其中，S是所有以i为弧尾的弧的集合。
两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。
4、 求关键路径的算法
（1） 输入e条弧<j,k>；，建立AOE网的存储结构。
（2） 从源点v1出发，令ve（1）=0，求 ve(j) 2<=j<=n。
（3） 从汇点vn出发，令vl(n)=ve(n），求 vl(i) 1<=i<=n-1。
（4） 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s）和最晚开始时间l(s），其中e(s)=l(s）的为关键活动。
求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。
Status ToplogicalSort(ALGraph G,stack &T){
FindInDegree(G,indegree);
InitStack(S);count=0; ve[0..G.vexnum-1]=0;
while(!StackEmpty(S))
{ Pop(S,j);Push(T,j); ++count;
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{k=p>adjvex;
if(--indegree[k]==0) Push(S,k);
if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info);
}
}
if(count<G.vexnum) return ERROR;
else return OK;
}
status CriticalPath(ALGraph G){
if(!ToplogicalOrder(G,T)) return ERROR;
vl[0..G.vexnum-1]=ve[G.vexnum-1];
while(!StackEmpty(T))
for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)
{k=p->adjvex; t=*(p->info);
if(vl[k]-t<vl[j]) vl[j]=vl[k]-t;
}
for(j=0;j<G.vexnum;++j)
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{k=p>adjvex; t=*(p->info);
ee=ve[j]; el=vl[k];
tag=(ee==el)?’*’：’’；
printf(j,kt,ee,el,tag);
}
} （1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；
（2） 只有缩短关键活动的工期才有可能缩短工期；
（3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期；
（4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。 #include <iostream>
#include <cstdio>
#include<string.h>
using namespace std;
int n,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];
void init()
{
int i,a,b,c;
scanf(%d%d,&n,&m);
for (i=1;i<=m;i++)
{
scanf(%d%d%d,&a,&b,&c);
w[a][b]=c;
prev[b]++;
}
}
inline void Newq(int v)
{
r++;
queue[r]=v;
}
inline void Del(int v)
{
int i;
for (i=1;i<=n;i++)
if (w[v][i])
{
prev[i]--;
if (!prev[i])
Newq(i);
}
}
void topo()
{
for (int i=1;i<=n;i++)
if (!prev[i])
Newq(i);
while (r<n)
{
l++;
Del(queue[l]);
}
}
void crucialpath()
{
int i,j;
memset(Time,0,sizeof(Time));
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((w[j][queue[i]]) && (Time[j]+w[j][queue[i]]>Time[queue[i]]))
{
Time[queue[i]]=Time[j]+w[j][queue[i]];
Pos[queue[i]]=j;
}
}
void print()
{
printf(%d\n,Time[n]);
int i=n,k=0;
while (i!=1)
{
k++;
path[k]=i;
}
for (i=k;i>1;i--)
printf(%d ,path[i]);
printf(%d\n,path[1]);
}
int main()
{
init();
topo();
crucialpath();
print();
return 0;
}
