数据结构与算法分析.ppt

表示实际工程计划的AOE网应该是无环的，并且存在唯一 的入度为0的开始顶点（源点）和唯一的出度为0的结束点 （汇点）。
2019-8-21
谢谢观赏
4
AOE网研究的主要问题：
如果用AOE 网表示一项工程，那么仅仅考虑各个子工程 之间的优先关系还不够，更多地是关心整个工程完成的最 短时间是多少，哪些活动的延迟将影响整个工程进度,而加 速这些活动能否提高整个工程的效率,因此AOE网有待研 究的问题是: (1) 完成整个工程至少需要多少时间？ (2) 哪些活动是影响工程进度的关键活动？
2019-8-21
谢谢观赏
21
正拓扑顺序？
队列变化？ 最后的front,rear值？
a1=4 1
2 a3=14 a4=10
a7=6
5 a8=8
4 a6=8
7 a10=12 8
a2=12 3
a5=18
6 a9=6
2019-8-21
谢谢观赏
22
求Ve(k)
01 2 34 5 6 7 Ve(k) 00 08 012 022 028 040 3406 508
ve(j):事件vj的最早发生时间。事件用v标识，事件 的编号用括号中的数字标识，v的下标区分“最早” 和“最晚”。 vl(j):事件vj的最晚发生时间。
事件用“发生”描述。 e(i):活动ai的最早开始时间。没有v的符号就是表
示活动，括号中是活动的编号，e表示最早开始时 间，l表示最晚。 l(i):活动ai的最晚开始时间。 活动用“开始”
数据结构与算法分析
第六章 关键路径（5）
2019-8-21
谢谢观赏
1
6.7 关键路径
(1) 如何建立一个工程进度控制模型？如何估算完成整个工 程至少需要多少时间(假设网络中没有环)?
(2) 为缩短完成工程所需的时间, 应当加快哪些活动? (3) 人们用AOE网解决这个问题
2019-8-21
谢谢观赏
if(dig[i].id==0) tpord[++rear]=i;
2019-8-21
谢谢观赏
19
m=0;}
//计数拓扑排序的顶点数
Step1:求Ve(k)
从源点V1出发，令Ve(1) = 0，按拓扑序列次序求出其余各 顶点事件的最早发生时间:
Ve(k) = max{ Ve(j)+ACT[j][k] } j∈T
不止一条。这些路径的长度也可能不同。完成不同路径 的活动所需的时间虽然不同，但只有各条路径上所有活 动都完成了，整个工程才算完成。
因此，完成整个工程所需的时间取决于从源点到汇点的 最长路径长度，即在这条路径上所有活动的持续时间之 和。这条路径长度最长的路径就叫做关键路径(Critical Path)。
在关键路径长度的范围内，可以安排并行的活动
2019-8-21
谢谢观赏
6
举例：奥运会竞赛日程
地点：主会场 需要考虑的场地：中心、跑道、沙坑 需要考虑的项目：短跑、长跑、马拉松、铅球、跳高、跳
远。。。 源点：开幕式;终点:闭幕式
2019-8-21
谢谢观赏
7
术语： ve(j),vl(j), e(i), l(i),
2019-8-21
//AoE网数据表示
谢谢观赏
17
数据结构：Ve，Vl，e，l
数组 int vl[n],ve[n]; int l[maxsize],e[maxsize];
拓扑：队列： tpord[n]； int front=-1,rear=-1;
2019-8-21
谢谢观赏
18
初始化
void criticalpath(vexnode dig[])
tpord 12345678
8
28
2
5
a1=8
0
a7=6 a3=14 22
1
4
a2=12 1a24=10
a6=8
40
3 2019-8-21
6
a5=28
a8=8
3466a10=12 58
7
8
a9=6 谢谢观赏
10 21 31 42 51 62 72 81
2
3
4
4
6
5
6
7
7
8
23
Step2(回退阶段)：
a7=6
5 a8=8
4 a6=8
7 a10=12 8
a =12 2 2019-8-21
3
a5=28 6 谢谢观赏
a9=6
16
数据结构：AOE图
typedef struct node
2
5
{ int adjvex; int dur; struct node *next;
a1=8 1
a3=14
a4=10
a7=6 4 a6=8
}edgenode;//边表结点 a2=12 3 a5=28 6
a8=8 7 a10=12 8
a9=6
typedef struct
{ vextype vertex;
//顶点标识
int id;
//入度
edgenode *link;
//指向出边表
}vexnode;
//顶点表结点
vexnode dig[n];
while(p)//遍历j的所有出边(j,k),改vl[j]
{ k=p->adjvex;
if(vl[k]-p->dur<vl[j])
while(p)//遍历j的所有出边，修改ve[k]
{ k=p->adjvex;
dig[k].id--;
if(ve[j]+p->dur>ve[k])
ve[k]=ve[j]+p->dur;
if(dig[k].id==0)
tpord[++rear]=k;
p=p->next; }
}
if(m<n)
printf("\n the network has a cycle\n");
201•9-V8-2e1 (6)是多少？
谢谢观赏
9
e(i):活动ai 的最早可能开始时间
e(i)= Ve(j) …………..( 1 )
j ai
2
5
a1=8 1
a3=14 a4=10
a7=6 4 a6=8
a8=8 7 a10=12 8
a2=12 3
a5=28
6 a9=6
若活动ai 在边< Vj , Vk>上, 则e(i) 是顶点Vj 最早时间。事 件Vj发生，表明以Vj为终点的活动全部结束。所以，以Vj 为起点的所有活动ai可以立即开始。
if(ve[j]+p->dur>ve[k])
ve[k]=ve[j]+p->dur;
if(dig[k].id==0)
tpord[++rear]=k;
p=p->next;
}
20
求ve[k]
while(front!=rear) //栈非空循环,拓扑顺序遍历AOE求Ve[j]
{ front++; j=tpord[front]; m++; p=dig[j].link;
其中T是以顶点Vk为尾的所有边的顶点集合(2≤k≤n) 如果
网中有回路，不能求出关键路径则算法中止；否则转
Step2。
…
while(p)//遍历j的所有出边
{
j1 T Ve(j)
j ACT[j][k] k
….
j2 …. jn
2019-8-21
模型
j
k
jn 方法谢谢观赏
k=p->adjvex;
dig[k].id--;
l(i) = e(i) …………..( 3 )
l(i) = e(i)表示活动是没有时间余量的关键活动。由上述分 析知，为找出关键活动，需要求各个活动的e(i)与l(i)，以
判别一个活动ai是否满足l(i) = e(i)。
Ve(k) 和Vl(k)可由拓扑排序算法得到。
e(i)： e(i)＝ Ve(j)
2019-8-21
谢谢观赏
10
Vl(k)：事件Vk的最迟发生时间
是在保证汇点Vn在Ve(n)时刻完成的前提下，事件Vk的允
许的最迟开始时间。在不推迟工期的情况下，一个事件最
迟发生时间Vl(k)应该等于汇点的最早发生时间Ve(n )减去
从Vk到Vn的最大路径长度。 28
24 5
Ve(n )：58
关键活动，就可以找到关键路径.
2019-8-21
谢谢观赏
15
基本思路：
1. 拓扑排序,并求出Ve(k) ， 2. 逆拓扑排序，求Vl(k) 3. 根据公式和权值邻接矩阵ACT[N][N]求e（i），l（i） 4. 根据e（i），l（i）求出关键活动 5. 根据关键活动求出关键路径
a1=8 1
2 a3=14 a4=10
2019-8-21
谢谢观赏
8
Ve(j) ：事件vj的最早发生时间
Ve(j)＝从源点V1 到顶点Vj 的最长路径长度。
2
5
a1=8 1
a3=14 a4=10
a7=6 4 a6=8
a8=8 7 a10=12 8
a2=12 3
a5=28
6 a9=6
•从源点到顶点Vj的最长路径，可以包括所有以顶点Vj 为终点的全部活动所需时间。经过这段路径，事件Vj才 有可能发生。
Vj ai Vk
是指在不会引起工期延误的前提下，活动ai允许的最迟 开始时间。因为事件Vk发生表明以Vk为终点的入边所表 示的所有活动均已完成，所以事件Vk的最迟发生时间Vl(k) 也是所有以Vk为终点的入边<Vj , Vk>所表示的活动ai可 以最迟完成时间。显然，为不推迟工期，活动ai的最迟开 始时间Ll(i)应该是ai的最迟完成时间Vl(k)减去ai的持续时 间，即