关键路径(AOE网)

关键路径(AOE网)关键路径(AOE网)

求解步骤:

1.对顶点进行拓扑排序,求出每个事件(顶点)的最早发生时间(ve);

2.按照顶点的逆拓扑排序,求出每个事件的最晚发生时间(vl);

3.计算每个活动(弧)的最早开始时间(ee)和最晚开始时间(el);

4.找出关键活动,即 ee = el 的弧。

思考:

1.事件最早发生时间 = Max(前一事件最早发生时间 + 活动持续时间(dul));

2.事件最迟发生时间 = Min(后一事件最迟发生时间 + 活动持续时间);

3.活动最早开始时间 = 前一事件的最早发生时间;

4.活动最迟开始时间 = 后一事件的最迟发生时间 - 活动持续时间。

核心代码:

CriticalPath函数

 1 void CriticalPath(OLGraph* G)
 2 {
 3     int i = 0, j = 0, k = 0;
 4     int dut = 0;//活动持续时间
 5     int el = 0;//活动最迟开始时间
 6     int ee = 0;//活动最早开始时间
 7     int vl[MAXVEX] = { 0 };//事件最迟发生时间
 8     int ve[MAXVEX] = { 0 };//事件最早发生时间
 9     ArcNode* P = NULL;
10     SeqStack T;
11 
12     T.top = -1;
13     TopoSort(G, &T, ve);
14 
15     for (i = 0; i < G->vexnum; i++)
16     {
17         vl[i] = ve[G->vexnum - 1];
18     }
19 
20     while (T.top != -1)
21     {
22         PopStack(&T, &i);
23         //按拓扑逆序求各顶点的vl值
24         for (P = G->vex[i].tail; P; P = P->tnext)
25         {
26             j = P->headvex;
27             dut = P->weight;
28             if (vl[j] - dut < vl[i])//事件 i 最迟发生时间
29             {
30                 vl[i] = vl[j] - dut;
31             }
32         }
33     }
34 
35     printf("关键路径:\n");
36     for (i = 0; i < G->vexnum; i++)
37     {
38         P = G->vex[i].tail;
39         while (P)
40         {
41             k = P->headvex;
42             ee = ve[i];
43             el = vl[k] - P->weight;
44             if (ee == el)
45             {
46                 printf("%c--%c\n", G->vex[i].vexdata, G->vex[k].vexdata);
47             }
48             P = P->tnext;
49         }
50     }
51 }

 TopoSort函数

 1 void TopoSort(OLGraph* G, SeqStack* T, int* ve)
 2 {
 3     int i = 0, j = 0, count = 0;
 4     int indegree[MAXVEX] = { 0 };
 5     ArcNode* P = NULL;
 6     SeqStack S;
 7 
 8     //degree数组存放各顶点入度
 9     for (i = 0; i < G->vexnum; i++)
10     {
11         P = G->vex[i].head;
12         while (P)
13         {
14             indegree[i]++;
15             P = P->hnext;
16         }
17     }
18 
19     S.top = -1;//栈初始化
20     for (i = 0; i < G->vexnum; i++)
21     {
22         if (indegree[i] == 0)
23         {
24             PushStack(&S, i);
25         }
26     }
27 
28     while (S.top != -1)    //拓扑排序
29     {
30         count++;
31         PopStack(&S, &i);
32         PushStack(T, i);
33         for (P = G->vex[i].tail; P; P = P->tnext)
34         {
35             j = P->headvex;
36             if (--indegree[j] == 0)
37             {
38                 PushStack(&S, j);
39             }
40             if ((ve[i] + P->weight) > ve[j])//事件 j 的最早发生时间
41             {
42                 ve[j] = ve[i] + P->weight;
43             }
44         }
45     }
46 
47     if (count < G->vexnum)
48     {
49         printf("该有向图有回路");
50         exit(1);
51     }
52 }

源代码:

关键路径(AOE网)
  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #define MAXVEX 20
  5 
  6 typedef struct ArcNode
  7 {
  8     int weight;
  9     int tailvex, headvex;
 10     struct ArcNode *tnext, *hnext;
 11 }ArcNode;
 12 
 13 typedef struct VexNode
 14 {
 15     char vexdata;
 16     ArcNode *tail, *head;
 17 }VexNode;
 18 
 19 typedef struct
 20 {
 21     int vexnum, arcnum;
 22     VexNode vex[MAXVEX];
 23 }OLGraph;//十字链表
 24 
 25 typedef struct
 26 {
 27     int top;
 28     int elem[MAXVEX];
 29 }SeqStack;//定长顺序栈
 30 
 31 void PushStack(SeqStack* S, int vex)
 32 {
 33     if (S->top == MAXVEX - 1)
 34     {
 35         printf("栈满");
 36         exit(1);
 37     }
 38     else
 39     {
 40         S->top++;
 41         S->elem[S->top] = vex;
 42     }
 43 }
 44 
 45 void PopStack(SeqStack* S, int* vex)
 46 {
 47     if (S->top == -1)
 48     {
 49         printf("空栈");
 50         exit(1);
 51     }
 52     else
 53     {
 54         (*vex) = S->elem[S->top];
 55         S->top--;
 56     }
 57 }
 58 
 59 void TopoSort(OLGraph* G, SeqStack* T, int* ve)
 60 {
 61     int i = 0, j = 0, count = 0;
 62     int indegree[MAXVEX] = { 0 };
 63     ArcNode* P = NULL;
 64     SeqStack S;
 65 
 66     //degree数组存放各顶点入度
 67     for (i = 0; i < G->vexnum; i++)
 68     {
 69         P = G->vex[i].head;
 70         while (P)
 71         {
 72             indegree[i]++;
 73             P = P->hnext;
 74         }
 75     }
 76 
 77     S.top = -1;//栈初始化
 78     for (i = 0; i < G->vexnum; i++)
 79     {
 80         if (indegree[i] == 0)
 81         {
 82             PushStack(&S, i);
 83         }
 84     }
 85 
 86     while (S.top != -1)    //拓扑排序
 87     {
 88         count++;
 89         PopStack(&S, &i);
 90         PushStack(T, i);
 91         for (P = G->vex[i].tail; P; P = P->tnext)
 92         {
 93             j = P->headvex;
 94             if (--indegree[j] == 0)
 95             {
 96                 PushStack(&S, j);
 97             }
 98             if ((ve[i] + P->weight) > ve[j])//事件 j 的最早发生时间
 99             {
100                 ve[j] = ve[i] + P->weight;
101             }
102         }
103     }
104 
105     if (count < G->vexnum)
106     {
107         printf("该有向图有回路");
108         exit(1);
109     }
110 }
111 
112 void CriticalPath(OLGraph* G)
113 {
114     int i = 0, j = 0, k = 0;
115     int dut = 0;//活动持续时间
116     int el = 0;//活动最迟开始时间
117     int ee = 0;//活动最早开始时间
118     int vl[MAXVEX] = { 0 };//事件最迟发生时间
119     int ve[MAXVEX] = { 0 };//事件最早发生时间
120     ArcNode* P = NULL;
121     SeqStack T;
122 
123     T.top = -1;
124     TopoSort(G, &T, ve);
125 
126     for (i = 0; i < G->vexnum; i++)
127     {
128         vl[i] = ve[G->vexnum - 1];
129     }
130 
131     while (T.top != -1)
132     {
133         PopStack(&T, &i);
134         //按拓扑逆序求各顶点的vl值
135         for (P = G->vex[i].tail; P; P = P->tnext)
136         {
137             j = P->headvex;
138             dut = P->weight;
139             if (vl[j] - dut < vl[i])//事件 i 最迟发生时间
140             {
141                 vl[i] = vl[j] - dut;
142             }
143         }
144     }
145 
146     printf("关键路径:\n");
147     for (i = 0; i < G->vexnum; i++)
148     {
149         P = G->vex[i].tail;
150         while (P)
151         {
152             k = P->headvex;
153             ee = ve[i];
154             el = vl[k] - P->weight;
155             if (ee == el)
156             {
157                 printf("%c--%c\n", G->vex[i].vexdata, G->vex[k].vexdata);
158             }
159             P = P->tnext;
160         }
161     }
162 }
163 
164 //返回图G中顶点vex的位置
165 int LocateVex(OLGraph* G, char vex)
166 {
167     int i = 0;
168     for (i = 0; i < G->vexnum; i++)
169     {
170         if (G->vex[i].vexdata == vex)
171         {
172             return i;
173         }
174     }
175     return -1;
176 }
177 
178 void Create(OLGraph* G)
179 {
180     int weight = 0;
181     int i = 0, j = 0, k = 0;
182     char vex1 = 0, vex2 = 0;
183     ArcNode *P = NULL, * Pre = NULL;
184 
185     printf("请输入顶点数和边数(逗号分隔):");
186     scanf("%d%*c%d", &G->vexnum, &G->arcnum);
187     for (i = 0; i < G->vexnum; i++)
188     {
189         printf("请输入第%d个顶点:", i + 1);
190         scanf(" %c", &G->vex[i].vexdata);
191         G->vex[i].head = G->vex[i].tail = NULL;
192     }
193     for (k = 0; k < G->arcnum; k++)
194     {
195         printf("请输入第%d条边的弧尾、头和权值(逗号分隔):", k + 1);
196         scanf(" %c%*c%c%*c%d", &vex1, &vex2, &weight);
197         i = LocateVex(G, vex1);
198         j = LocateVex(G, vex2);
199         P = (ArcNode*)calloc(1, sizeof(ArcNode));
200         P->tailvex = i;
201         P->headvex = j;
202         P->weight = weight;
203         //在 j 为弧头的链表尾链接上P结点
204         if (!G->vex[j].head)
205         {
206             G->vex[j].head = P;
207         }
208         else
209         {
210             Pre = G->vex[j].head;
211             while (Pre->hnext)
212             {
213                 Pre = Pre->hnext;
214             }
215             Pre->hnext = P;
216         }
217         //在 i 为弧尾的链表尾链接上P结点
218         if (!G->vex[i].tail)
219         {
220             G->vex[i].tail = P;
221         }
222         else
223         {
224             Pre = G->vex[i].tail;
225             while (Pre->tnext)
226             {
227                 Pre = Pre->tnext;
228             }
229             Pre->tnext = P;
230         }
231     }
232 }
233 
234 int main(void)
235 {
236     OLGraph G;
237     Create(&G);
238     CriticalPath(&G);
239     system("pause");
240     return 0;
241 }
源代码

 

上一篇:过滤器和拦截器区别


下一篇:07.AOE网和图的关键路径