关键路径

本文最后更新于:2021年11月28日 晚上

室友是信息与计算科学专业的学生,他们的小学期项目是实现老师所给的算法题目中的一个。我给他选择的题目是计算==关键路径==。
这个算法本来在我所学的数据结构课上,不属于要求可以代码实现的算法中,但是我了解过计算方法,所以觉得实现起来还算简单。

本问题的数据结构为有向无环图,弧的起点为先决事件,终点为后续事件,弧的权重为事件的执行时间。

本问题还需明确的概念有:

  1. 事件的最早执行时间:由于有的事件的先决事件有多个,那么需要等待所有先决事件执行完成,才可执行目标事件,故此事件的最早执行时间即为——所有先决事件完成的最迟时间。
  2. 事件的最迟执行时间:在后续事件完成时间不变的前提下,后续时间减去,先决事件——后续事件所需时间,即为先决时间的最迟时间。
  3. 关键路径(事件):最早执行时间==最迟执行时间 的事件即为——关键事件

因此本问题的解题步骤即可归纳为:

  1. 输入数据:使用邻接矩阵存储数据
  2. 拓扑排序:判断是否存在环,存在无法计算
  3. 最早时间:
  4. 最迟时间:
  5. 输出路径:

输入数据

这没什么技术可言,自己到自己不可能存在路径故人为排除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void initEvent(int eventNumber,int ** eventContainer){
if (eventNumber==1){
cout<<"只有一个工程,那么关键项目则为其本身"<<endl;
system("pause");
exit(0);
}
for(int i=0;i<eventNumber;++i){
eventContainer[i]=new int [eventNumber]();
}
cout<<"OK!告诉我每个工程需要的执行时间吧"<<endl<<"默认从事件1开始执行"<<endl;
cout<<"请输入两个事件之间需要的时间(无关联请输入0!!!)"<<endl;
for(int i=0;i<eventNumber;++i){
for(int j=0;j<eventNumber;++j){
if(i!=j){
cout << i + 1 << "->" << j + 1 << ":";
cin >> eventContainer[i][j];
}
}
}

}

拓扑排序

这里我借助了STL标准库中的stack库函数

1
stack<int> eventStack;#新建栈,eventStack为栈名
1
k=eventStack.top();#用k获取栈顶元素,但并不会删除元素
1
eventStack.pop();#删除栈顶元素

根据拓扑排序的原理:

  1. 首先初始化一个栈,接着使用一维数组记录每个点的入度,遍历入度为0的点,将其入栈。
  2. 将栈顶元素出栈,并将其后继元素的入度减一即——从图中删除该点,若减一之后入度为零,则入栈。
  3. 继续执行步骤2,至无入度为零点。若这时还有点余下,则表明图中存在环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int topoLogicalSort(int eventNumber ,int ** eventContainer,int *earliestTime){
stack<int> eventStack;
int count ,k;
int * indegree =new int[eventNumber]();
for(int i=0;i<eventNumber;++i){
int sum=0;
for(int j=0;j<eventNumber;++j){
if(eventContainer[j][i]!=0) ++sum;
}
indegree[i]=sum;
if(indegree[i]==0) eventStack.push(i);
}
count=0;
while(!eventStack.empty()){
k=eventStack.top();
eventStack.pop();
++count;
for(int i=0;i<eventNumber;++i){
if(eventContainer[k][i]!=0){
if(!(--indegree[i])) eventStack.push(i);
initEarliestTime(earliestTime,eventContainer,k,i);
}
}
}
if(count<eventNumber) return 0;
else return 1;

}

最早时间

在本段代码中,有一条语句,实际上是在计算每个事件的最早时间。

因为拓扑排序的过程,实际上也就是从最开始的事件到最终事件的顺序,可以在拓扑排序时,按照事件的相关性,通过先决事件和所需时间计算后续事件。

通过计算:先决时间的最早完成时间+先决——后续事件的所需时间。在有多个先决事件时,计算其中最大值。

1
initEarliestTime(earliestTime,eventContainer,k,i);
1
2
void initEarliestTime(int * earliestTime,int ** eventContainer,int k,int i){
if(earliestTime[k]+eventContainer[k][i]>earliestTime[i]) earliestTime[i]=earliestTime[k]+eventContainer[k][i];

最迟时间

由于最迟时间是由后续事件计算先决事件,所以在事件最早时间计算完成后,就可以进行计算了。

通过计算:后续事件的最早事件-先决——后续所需时间。在有多个后续时间时,计算其中最小值。

1
2
3
4
5
6
7
8
void initLatestTime(int * ealiestTime,int * latestTime ,int ** eventContainer,int eventNumber){
for(int i=eventNumber-2;i>=0;--i){
for(int j=0;j<eventNumber;++j){
if(eventContainer[i][j]!=0){
if(latestTime[i]>latestTime[j]-eventContainer[i][j]) latestTime[i]=latestTime[j]-eventContainer[i][j];
}
}
}

输出路径

最早与最迟时间相等的即为关键路径

1
2
3
4
5
6
7
void criticalPath(int * ealiestTime,int * latestTime ,int eventNumber){
cout<<"关键项目为:";
for(int i=0;i<eventNumber;++i){
if(ealiestTime[i]==latestTime[i]) cout<<i<<" ";
}
return;
}

附全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <stdio.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std ;
void initEvent(int eventNumber,int ** eventContainer);
int topoLogicalSort(int eventNumber ,int ** eventContainer,int *earliestTime);
void initEarliestTime(int * earliestTime,int ** eventContainer,int k,int i);
void initLatestTime(int * ealiestTime,int * latestTime ,int ** eventContainer,int eventNumber);
void criticalPath(int * ealiestTime,int * latestTime ,int eventNumber);

int main() {
int eventNumber;
cout<<"请输入工程数量:";
cin>>eventNumber;
int ** eventContainer=new int * [eventNumber]();
int * earliestTime=new int[eventNumber]();
int * latestTime=new int[eventNumber]();
initEvent(eventNumber,eventContainer);
if(!topoLogicalSort(eventNumber,eventContainer,earliestTime)){
cout<<"输入的工程路径似乎有一些问题"<<endl;
return 0;
}
cout<<"求得的项目最早完成时间为:";
for (int j = 0; j < eventNumber; ++j) {
latestTime[j]=earliestTime[eventNumber-1];
cout << earliestTime[j] <<" ";
}
cout<<endl;
initLatestTime(earliestTime,latestTime,eventContainer,eventNumber);
cout<<"求得的项目最迟完成时间为:";
for (int j = 0; j < eventNumber; ++j) {
cout << latestTime[j] <<" ";
}
criticalPath(earliestTime,latestTime,eventNumber);
return 0;
}
void initEvent(int eventNumber,int ** eventContainer){
if (eventNumber==1){
cout<<"只有一个工程,那么关键项目则为其本身"<<endl;
system("pause");
exit(0);
}
for(int i=0;i<eventNumber;++i){
eventContainer[i]=new int [eventNumber]();
}
cout<<"OK!告诉我每个工程需要的执行时间吧"<<endl<<"默认从事件1开始执行"<<endl;
cout<<"请输入两个事件之间需要的时间(无关联请输入0!!!)"<<endl;
for(int i=0;i<eventNumber;++i){
for(int j=0;j<eventNumber;++j){
if(i!=j){
cout << i + 1 << "->" << j + 1 << ":";
cin >> eventContainer[i][j];
}
}
}

}
int topoLogicalSort(int eventNumber ,int ** eventContainer,int *earliestTime){
stack<int> eventStack;
int count ,k;
int * indegree =new int[eventNumber]();
for(int i=0;i<eventNumber;++i){
int sum=0;
for(int j=0;j<eventNumber;++j){
if(eventContainer[j][i]!=0) ++sum;
}
indegree[i]=sum;
if(indegree[i]==0) eventStack.push(i);
}
count=0;
while(!eventStack.empty()){
k=eventStack.top();
eventStack.pop();
++count;
for(int i=0;i<eventNumber;++i){
if(eventContainer[k][i]!=0){
if(!(--indegree[i])) eventStack.push(i);
initEarliestTime(earliestTime,eventContainer,k,i);
}
}
}
if(count<eventNumber) return 0;
else return 1;

}
void initEarliestTime(int * earliestTime,int ** eventContainer,int k,int i){
if(earliestTime[k]+eventContainer[k][i]>earliestTime[i]) earliestTime[i]=earliestTime[k]+eventContainer[k][i];
}
void initLatestTime(int * ealiestTime,int * latestTime ,int ** eventContainer,int eventNumber){
for(int i=eventNumber-2;i>=0;--i){
for(int j=0;j<eventNumber;++j){
if(eventContainer[i][j]!=0){
if(latestTime[i]>latestTime[j]-eventContainer[i][j]) latestTime[i]=latestTime[j]-eventContainer[i][j];
}
}
}
}
void criticalPath(int * ealiestTime,int * latestTime ,int eventNumber){
cout<<"关键项目为:";
for(int i=0;i<eventNumber;++i){
if(ealiestTime[i]==latestTime[i]) cout<<i<<" ";
}
return;
}

关键路径
https://siegelion.cn/2018/12/12/关键路径/
作者
siegelion
发布于
2018年12月12日
许可协议