数据结构与算法分析课件

数据结构与算法分析第六章关键路径（5）1感谢你的观看2019年8月21数据结构与算法分析第六章关键路径（5）1感谢你的观看2016.7关键路径如何建立一个工程进度控制模型？如何估算完成整个工程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间,应当加快哪些活动?人们用AOE网解决这个问题2感谢你的观看2019年8月216.7关键路径如何建立一个工程进度控制模型？如何估算完成整AOE网（ActivityOnEdgeNetwork）在带权的有向图中，用结点表示事件：所有入边上进行的活动均已完成的事件用边表示活动：起始结点事件发生后所开展的活动边的上权表示活动的开销（如持续时间）则称此有向图为“边表示活动的网络”,简称AOE网。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=103感谢你的观看2019年8月21AOE网（ActivityOnEdgeNetwork）AOE网的性质活动开始时间：只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;事件发生时间：只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。4感谢你的观看2019年8月21AOE网的性质活动开始时间：只有在某个顶点所代表的事件发生后AOE网研究的主要问题：

如果用AOE网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此AOE网有待研究的问题是:(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键活动？5感谢你的观看2019年8月21AOE网研究的主要问题：如果用AOE网表示一项工路径长度、关键路径、关键活动：路径长度：是指从源点到汇点路径上所有活动的持续时间之和。关键路径：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。一个AOE中，关键路径可能不只一条。关键活动：关键路径上的活动称为关键活动。在关键路径长度的范围内，可以安排并行的活动6感谢你的观看2019年8月21路径长度、关键路径、关键活动：6感谢你的观看2019年8月2举例：奥运会竞赛日程地点：主会场需要考虑的场地：中心、跑道、沙坑需要考虑的项目：短跑、长跑、马拉松、铅球、跳高、跳远。。。源点：开幕式;终点:闭幕式7感谢你的观看2019年8月21举例：奥运会竞赛日程地点：主会场7感谢你的观看2019年8月术语：ve(j),vl(j),e(i),l(i),ve(j):事件vj的最早发生时间。事件用v标识，事件的编号用括号中的数字标识，v的下标区分“最早”和“最晚”。vl(j):事件vj的最晚发生时间。事件用“发生”描述。e(i):活动ai的最早开始时间。没有v的符号就是表示活动，括号中是活动的编号，e表示最早开始时间，l表示最晚。l(i):活动ai的最晚开始时间。活动用“开始”8感谢你的观看2019年8月21术语：ve(j),vl(j),e(i),l(i),veVe(j)：事件vj的最早发生时间Ve(j)＝从源点V1到顶点Vj的最长路径长度。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10从源点到顶点Vj的最长路径，可以包括所有以顶点Vj为终点的全部活动所需时间。经过这段路径，事件Vj才有可能发生。Ve(6)是多少？9感谢你的观看2019年8月21Ve(j)：事件vj的最早发生时间Ve(j)＝从源点V1e(i):活动ai的最早可能开始时间

若活动ai在边<Vj,Vk>上,则e(i)是顶点Vj最早时间。事件Vj发生，表明以Vj为终点的活动全部结束。所以，以Vj为起点的所有活动ai可以立即开始。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10e(i)=Ve(j)…………..(1)jai10感谢你的观看2019年8月21e(i):活动ai的最早可能开始时间若活动aiVl(k)：事件Vk的最迟发生时间是在保证汇点Vn在Ve(n)时刻完成的前提下，事件Vk的允许的最迟开始时间。在不推迟工期的情况下，一个事件最迟发生时间Vl(k)应该等于汇点的最早发生时间Ve(n)减去从Vk到Vn的最大路径长度。还有什么含义？以vk为终点的活动的最迟完成时间。1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=2a3=14a4=10Ve(n)：582240244658Ve(4)：22Vl(4)：32＝58－26261282011感谢你的观看2019年8月21Vl(k)：事件Vk的最迟发生时间是在保证汇点Vn在Ve(nL(i)

：活动ai的最迟允许开始时间

是指在不会引起工期延误的前提下，活动ai允许的最迟开始时间。因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间Vl(k)也是所有以Vk为终点的入边<Vj,Vk>所表示的活动ai可以最迟完成时间。显然，为不推迟工期，活动ai的最迟开始时间Ll(i)应该是ai的最迟完成时间Vl(k)减去ai的持续时间，即l(i)=Vl(k)-ACT[j][k]…………..(2)

其中,ACT[j][k]是活动ai的持续时间（<Vj,Vk>上的权）。VkaiVj12感谢你的观看2019年8月21L(i)：活动ai的最迟允许开始时间L(i)-e(i)表示活动ai的最早可能开始时间和最迟允许开始时间的时间余量。关键路径上的活动都满足：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)l(i)：

l(i)=Vl(k)-ACT[j][k]⑤时间余量l(i)-e(i)jaikaikj13感谢你的观看2019年8月21L(i)-e(i)表示活动ai的最早可能开始时间和最迟思考：完成整个工程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间,应当加快哪些活动?分析：在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。14感谢你的观看2019年8月21思考：完成整个工程至少需要多少时间(假设网络中没有环)?14关键路径与关键活动复习关键路径概念：完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键活动概念：那些满足l(i)=e(i)的活动ai关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.15感谢你的观看2019年8月21关键路径与关键活动复习关键路径概念：完成工程的最短时间是从源基本思路：拓扑排序,并求出Ve(k)，逆拓扑排序，求Vl(k)根据公式和权值邻接矩阵ACT[N][N]求e（i），l（i）根据e（i），l（i）求出关键活动根据关键活动求出关键路径1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1016感谢你的观看2019年8月21基本思路：拓扑排序,并求出Ve(k)，1324a1=8a数据结构：AOE图typedefstructnode{ intadjvex; intdur; structnode*next;}edgenode;//边表结点typedefstruct{ vextypevertex; //顶点标识

intid; //入度

edgenode*link; //指向出边表}vexnode; //顶点表结点vexnodedig[n]; //AoE网数据表示1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=1017感谢你的观看2019年8月21数据结构：AOE图typedefstructnode13数据结构：Ve，Vl，e，l数组intvl[n],ve[n]; intl[maxsize],e[maxsize];拓扑：队列：

tpord[n]；intfront=-1,rear=-1;18感谢你的观看2019年8月21数据结构：Ve，Vl，e，l数组18感谢你的观看2019年8初始化voidcriticalpath(vexnodedig[]){ inti,j,k,m; intfront=-1,rear=-1; //用队列。顺序队列的首尾指针初值

inttpord[n],vl[n],ve[n]; intl[maxsize],e[maxsize]; edgenode*p; for(i=0;i<n;i++)初始化，建立入度为0的队列。{ ve[i]=0; if(dig[i].id==0) tpord[++rear]=i; m=0;} //计数拓扑排序的顶点数19感谢你的观看2019年8月21初始化voidcriticalpath(vexnodeStep1:求Ve(k)

从源点V1出发，令Ve(1)=0，按拓扑序列次序求出其余各顶点事件的最早发生时间:Ve(k)=max{Ve(j)+ACT[j][k]}j∈T

其中T是以顶点Vk为尾的所有边的顶点集合(2≤k≤n)

如果网中有回路，不能求出关键路径则算法中止；否则转Step2。jkj2jnj1TVe(j)ACT[j][k]….….…模型方法jkjnwhile(p)//遍历j的所有出边{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;}20感谢你的观看2019年8月21Step1:求Ve(k)从源点V1出发，令Ve(求ve[k] while(front!=rear)//栈非空循环,拓扑顺序遍历AOE求Ve[j] { front++;j=tpord[front]; m++; p=dig[j].link; 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("\nthenetworkhasacycle\n");21感谢你的观看2019年8月21求ve[k] while(front!=rear)//栈非正拓扑顺序？队列变化？最后的front,rear值？1324a1=4a2=125678a10=12a9=6a8=8a5=18a6=8a7=6a3=14a4=1022感谢你的观看2019年8月21正拓扑顺序？队列变化？1324a1=4a2=125678a1求Ve(k)1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10Ve(k)0123456746465778320128224028365834876521tpord12225836402880464623感谢你的观看2019年8月21求Ve(k)1324a1=8a2=125678a10=12aStep2(回退阶段)：从汇点Vn出发，令Vl(n)=Ve(n)，按逆拓扑有序求其余各顶点的最晚发生时间：Vl(j)=min{Vl(k)-ACT[j][k]}k∈S

其中S是以顶点Vj为头的所有边的尾顶点的集合(2≤j≤n-1)逆序的潜在条件jkknk2k1ACT[j][k]S模型while(p)//遍历j的所有出边(j,k),改vl[j]{k=p->adjvex;if(vl[k]-p->dur<vl[j]) vl[j]=vl[k]-p->dur;if(dig[k].id==0) tpord[++rear]=k;p=p->next;}24感谢你的观看2019年8月21Step2(回退阶段)：从汇点Vn出发，令Vl(n)=V求Vl[k] for(i=0;i<n;i++) vl[i]=ve[n-1]; //vl初值 for(i=n-2;i>=0;i--) //逆拓扑序列取结点

{ j=tpord[i]; p=dig[j].link; while(p) //遍历顶点j的所有出边(j,k)，修改vl[j] { k=p->adjvex; if(vl[k]-p->dur<vl[j]) vl[j]=vl[k]-p->dur; p=p->next; } }25感谢你的观看2019年8月21求Vl[k] for(i=0;i<n;i++) vl[i]58求Vl(k)1324a1=8a2=125678a10=12a9=6a8=8a5=28a6=8a7=6a3=14a4=10Vl(k)5858585858585812345678令“-”=0080706050403020114428610486651876712812382585858585858585834876521tpord46383212804638408032124026感谢你的观看2019年8月2158求Vl(k)1324a1=8a2=125678a10=1Step3：求每一项活动ai的最早开始时间:e(i)=Ve(j)最晚开始时间:l(i)=Vl(k)-ACT[j][k]若某条边满足e(i)=l(i)，则它是关键活动。为了简化算法,可以在求关键路径之前已经对各顶点实现拓扑排序