- 1、本文档共45页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
DS07_图04_拓扑排序和关键路径
v2 v7 v6 v5 v4 v1 v3 v9 v8 ve[j] vl[i] 0 6 4 5 7 7 16 14 18 18 14 16 10 7 8 6 6 0 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 ⑵ 事件的最迟发生时间vl[i] 在不推迟整个工程工期的前提下,活动ai最迟必须开始进行的时间。 vj vi 从终点出发递推: vl[终点]=ve[终点] vl[i]=Min{vl[j]-dutvi , vj}(vi , vj∈S) S为所有从vi 发出的有向边的集合 S ⑶ 活动的最早开始时间e[i] 若活动ai是由弧vj , vk表示,则活动ai的最早开始时间应等于事件vj的最早发生时间。因此,有: e[i]=ve[j] v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 v2 v7 v6 v5 v4 v1 v3 v9 v8 ve[j] 0 6 4 5 7 7 16 14 18 a2 a7 a6 a5 a4 a1 a3 a9 a8 e[i] 0 0 0 6 4 5 7 7 7 a10 a11 16 14 vk vj ai l[i] 10 7 7 8 6 6 3 2 0 16 14 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 a2 a7 a6 a5 a4 a1 a3 a9 a8 a10 a11 v2 v7 v6 v5 v4 v1 v3 v9 v8 vl[j] 18 14 16 10 7 8 6 6 0 活动ai的最晚开始时间是指,在不推迟整个工期的前提下, ai必须开始的最晚时间。 若ai由弧vj,vk表示,则ai的最晚开始时间要保证事件vk的最迟发生时间不拖后。因此,有: l[i]=vl[k]-dutvj, vk ⑷ 活动的最晚开始时间l[i] vk vj ai a2 a7 a6 a5 a4 a1 a3 a9 a8 e[i] l[i] 0 0 0 6 4 5 7 7 7 10 7 7 8 6 6 3 2 0 a10 a11 16 14 16 14 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 关键活动:l[i]=e[i]的活动 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 由此得到下述求关键路径的算法: 1)输入e条弧i,j,建立AOE网的存储结构。 2)从源点v0出发,令ve[0]=0按拓扑有序求其余各顶点的最早发生时ve[i](1≤i≤ n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤(3)。 3)从汇点vn出发,令vl[n-1]= ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i] (n-2 ≥i≥ 0); 4)根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s),则为关键活动。 如上所述,计算顶点的ve值是在拓扑排序的过程中进行的,需对拓扑排序的算法作如下修改: 1)在拓扑排序之前设初值,令ve(i)=0(0=in-1); 2)在算法中增加一个计算vi的直接后继vj的最早发生时间的操作:若 ve(i)+dut(i,j) ve(j), 则 ve(j) = ve(i)+dut(i,j); 3)为了能按逆拓扑有序序列的顺序计算各顶点的vl值,需记下在拓扑排序的过程中求得的拓扑有序序列,则需要在拓扑排序算法中,增设一个栈以记录拓扑有序序列,则在计算求得各顶点的 ve 值之后,从栈顶至栈底便为逆拓扑有序序列。 求最早发生时间ve的算法 Status TopologicalOrder(ALGraph G,Stack T){ //有向网G采用邻接表,求各顶点事件最早发生时间ve(全局变量) //T为拓扑序列顶点栈,s为零入度顶点栈。 ???? FindInDegre
文档评论(0)