数据结构第19讲关键路径与最短路径C.doc

第7章图7.1图的定义和术语7. 2图的存储结构7. 3图的遍历7.4图的连通性问题7.5有向无环图及其应用7. 5.1拓扑排序7. 5. 2关键路径7. 6最短路径7. 5. 2关键路径对整个工程和系统，人们关心的是两个方面 的问题：1） 工程能否顺利进行对AOV网进行拓扑排序2） 估算整个工程完成所必须的最短时间对AOE网求关键路径AOE-网■ AOE —网(Act i v ity On Edge Network):即边表示活动的网AOE网是一个带权的有向无环图其中:■顶点表示事件（Everrt） ■弧表示活动（Activity）■权值表示活动持续的时间通常可用AOE网来估算工程的完成时间■XJV1表示整个工程的开始与每个活动相联系的数是 执行该活动所需的时间上图AOE-网中:V5表示a4和已经完 成，a?和a*可以开始in]共有 11 项活动：ap a2, a3,共有9个事件：Vp v2f v3, ...v9,每个事件表示在它之 前的活动已经完成，在它之后的活动可以开始由于整个工程只有一个开始点和一个完成点，在正 常的情况（无环）下，网中只有一个入度为零的点（称 作源点）和一个出度为零的点（称作汇点）依据AOE-网可以研究什么问题?(1)完成整项工程至少需要多少时间?(2)哪些活动是影响工程进度的关键?完成工程的最短时间是从源点到汇点的最长路径的长度。

路径长度最长的路径叫做关键路径从％到勺的最长路径是(vp v2, v5, v8, v9),路径长度是1事件哲的最早发生时间假设开始点是论，从冷到Vj的最长路径长度叫做事V9的最早发生时间是18件5的最早发生时间这个时间决定了所有以Vi为尾的 弧所表示的活动的最早开始时间ffie(i)表示活动a)的最早开始时间活动的最迟开始时间Ki),这是在不推迟整个工程完 成的前提下，活动％最迟必须开始进行的时间的最早开始时间是5,最迟开始时间是8如推迟3天开 ，始或延迟3天完成，都不会影响整个工程的完成I⑴一e(i)两者之差意味着完成活动引的时间余量 我们把I⑴=e(i)的活动叫做关键活动显然，关键路径上的所有活动都是关键活动，因此提 前完成非关键活动并不能加快工程的进度由此可知：辨别关键活动就是找e(i) = l(i)的活动为求得AOE网中活动的e(i)和l(i),首先应求得事件的最早 发生时间ve(j)和最迟发生时间vl(j)o若活动引由弧＜i, j＞表示，持续时间记为dut«i, j» , 则有如下关系：活动i的最早开始时间等于事件j的最早发生时间 e(i) = ve(i)活动i的最迟开始时间等于事件k的最迟时间减去活动i 的持续时间I (i) = vl (j) - dut «i, j» 求ve(j)和vl (j)需分两步进行：ve[j]和vI [j]可以采用下面的递推公式计算:(1)向汇点递推ve (源点)=0 ；ve(j) = Max{ ve(i) + dut«i, j»}公式意义：从指向顶点气的弧的活动中取最晚完成的一 个活动的完成时间作为气的最早发生时间ve[j]（2）向源点递推由上一步的递推，最后总可求出汇点的最早发生时 间ve[n]o因汇点就是结束点，最迟发生时间与最早发生 时间相同，即vl[n]=ve[n]0从汇点最迟发生现时间vl [n] 开始,利用下面公式：© sVI （汇点）=ve （汇点）；vl (i) = Min{ vl (j) - dut«i, j» }公式意义：由从Vj顶点指出的弧所代表的活动中取需最早开始的一个开始时间作为K的最迟发生时间。

由此得到下述求关键路径的算法：1) 输入e条弧,建立AOE网的存储结构2) 从源点V出发，令ve[0] =0按拓扑有序求其余各顶点的 最早发生时ve[i] (iWiW n-1) o如果得到的拓扑有 序序列中顶点个数小于网中顶点数n,则说明网中存在 环，不能求关键路径，算法终止；否则执行步骤(3)3)从汇点Vn出发，令vl [n-1]= ve[n-1],按逆拓扑有序求 其余各顶点的最迟发生时间vl[i] (n-2 MiM 0)；4)根据各顶点的ve和v I值,求每条弧s的最早开始时间e(s)和最迟开始时间I (s) o若某条弧满足条件e (s) = I (s), 则为关键活动如上所述，计算顶点的ve值是在拓扑排序的过 程中进行的，需对拓扑排序的算法作如下修改：1)在拓扑排序之前设初值，令ve(i)=O (0<=i ve(j),则 ve(j)=ve(i) +dut «i, j» ；3) 为了能按逆拓扑有序序列的顺序计算各顶点的vl值, 需记下在拓扑排序的过程中求得的拓扑有序序列，则需要 在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则 在计算求得各顶点的ve值之后，从栈顶至栈底便为逆拓 扑有序序列。

总之，关键路径的求解操作包括:1）计算 ve[j]和 vl [j]①向汇点递推ve (源点)=0 ；ve(j) = Max { ve (i) + dut «i, j»}向源点递推2）判断Ki） = e（i）的活动（关键活动）vl (汇点)=ve(汇点);vl (i) = Min { vl (j) 一 dut«i, j»}求最早发生时间ve的算法Status Topological Order (ALGraph G, Stack &T) {//有向网G采用邻接表，求各顶点事件最早发生时间ve(全局变量) //T为拓扑序列顶点栈，s为零入度顶点栈Findl nDegree (G, i ndegree) ； //对各顶点求入度I n i tStack (S) ； //建零入度顶点栈Sfor (i=0； inextare){ k=p—>adjvex； //对i号顶点的每个邻接点的入度减I if (—indegree[k]==0) Push(S, k)； 〃若入度减为0,入栈 if (ve[j]+*(p->info)>ve[k] ) ve[k] =ve[j]+*(p->info)； } //for * (p-> i nfo) =dut «j, k»} //whiIif (countnextarc){k=p->adjvex； dut=* (p—> i nfo)； //dut if (vl [k]-dutnextarc){k=p->adjvex； dut=* (p—>info)；ee=ve[j]； el=vl [k]-dut； tag = (ee==e1) ?pr intf (j, k, dut, ee, el, tag) ； //输出关键活动}} //CriticalPath拓扑序列:V1、V3、V2、V5、V4、V6ve (源点)=0 ；ve(j) = Max{ ve(i) + dut«i, j»}vl (汇点)=ve (汇点)；vl (i) = Min { vl (j) 一 dut«i, j»}e(s) = ve (i)I (s) = vl (j) - dut «i, j»9练习：求下图AOE网的关键路径事件je、[j]UDI活动ie[i]L[i]L[i]-e[i]1001000266202234630334584660577546267in6583JL Vz716167770814148770918189710310161601114140总结：有向无环图是描述一项工程或系统的进行过 程的有效工具。

AOV网（顶点表示活动的有向网）与拓扑排序 一一解决工程或系统能否顺利进行；AOE网（边表示活动的有向网）和关键路径问题一一估算整个工程完成所必须的最短时间，求第7章图7.1图的定义和术语7. 2图的存储结构3图的遍历 4图的连通性问题 5有向无环图及其应用7. 6最短路径兮7. 6最短路径所谓最短路径问题是指：如果从图中某一顶 点（称为源点）出发到达另一顶点（称为终点） 的路径可能不止一条，如何找到一条路径使得沿 此路径上各边的权值总和达到最小1 -单源点最短路径7. 6.1单源点最短路径给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径始点终点D[i]最短路径vo V1 a>V2 10 (Vo/ V2)V3 50 (% V4/ V3)v4 30 (Vo/ V4)V5 60 (Vo/ V4f V3/ V5)如何在计算机中 求得最短路径？Dijkstra提出了一个按路径“长度”递增的 次序，逐步得到由给定源点到图的其余。