关键路径长度是整个工程所需的最短工期。
假设第 i 条弧为 <j, k>, 则 对第 i 项活动言:
Status TopologicalOrder(ALGraph G, SqStack &T){
FindInDegree(G, indegree); // 对各顶点求入度
InitStack(S);
InitStack(T);
for(i = 0; i < G.vexnum; i++)
if(!indegree[i]) Push(S, i);
count = 0; // 对输出顶点计数
for(i = 0; i < G.vexnum; i++)
ve[i] = 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])) Push(S, k);
if(ve[j] + *(p->info) > ve[k])
// 修改ve[j]
ve[k] = ve[j] + *(p->info);
}
}
if(count < G.vexnum){
cout << "图中有回路!";
return ERROR;
}
}
void Criticalpath(ALGraph G){
// G为有向网络,输出G的各项关键活动
for(i = 0; i < G.vexnum; i++)
vl[i] = ve[G.vexnum - 1]
while(!StackEmpty(T))
for(Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex;
dut = *(p->info);
if(vl[k] - dut < vl[j])
vl[j] = vl[k] - dut;
// dut是事件vj到事件vk活动的持续时间
}
for(j = 0; j < G.vexnum; ++j){
// 求活动的最早开始时间ee、最迟开始时间el和关键活动
for(p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex;
dut = *(p->info);
ee = ve[j];
el = vl[k] - dut;
tag = (ee == el)?'*':' ';
cout << j << " " << k << " " << dut <<" "
<< ee << " " << el << " " << tag << endl;
}
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。