DS07_图04_拓扑排序和关键路径.ppt

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