数据结构第19讲关键路径与最短路径.ppt
第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网(Activity On Edge Network)：即边表示活动的网。AOE网是一个带权的有向无环图。其中：顶点表示事件（Event）弧表示活动（Activity）权值表示活动持续的时间 通常可用AOE网来估算工程的完成时间。,上图AOE-网中：共有11项活动：a1,a2,a3,a11；共有9个事件：v1,v2,v3,v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。,v9表示整个工程的结束,v5表示a4和a5已经完成，a7和a8可以开始,与每个活动相联系的数是执行该活动所需的时间,v1表示整个工程的开始,由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（称作汇点）,汇点,源点,依据AOE-网可以研究什么问题？,（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？,完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径叫做关键路径。从v1到v9的最长路径是（v1,v2,v5,v8,v9），路径长度是18。,假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。用e(i)表示活动ai的最早开始时间。,V9的最早发生时间是18,事件vi的最早发生时间,l(i)e(i)两者之差意味着完成活动ai的时间余量。我们把l(i)e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。,a6的最早开始时间是5，最迟开始时间是8。如a6推迟3天开始或延迟3天完成，都不会影响整个工程的完成。,活动的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。,由此可知：辨别关键活动就是找e(i)l(i)的活动。为求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早发生时间 ve(j)和 最迟发生时间vl(j)。若活动ai由弧表示，持续时间记为dut()，则有如下关系：活动i的最早开始时间等于事件j的最早发生时间 e(i)ve(i)活动i的最迟开始时间等于事件k的最迟时间减去活动i的持续时间 l(i)vl(j)-dut()求ve(j)和 vl(j)需分两步进行：,vej和vlj可以采用下面的递推公式计算：（1）向汇点递推 ve(源点)=0；ve(j)=Max ve(i)+dut(),公式意义：从指向顶点Vj的弧的活动中取最晚完成的一个活动的完成时间作为Vj的最早发生时间vej,（2）向源点递推 由上一步的递推，最后总可求出汇点的最早发生时间ven。因汇点就是结束点，最迟发生时间与最早发生时间相同，即vln=ven。从汇点最迟发生现时间vln开始，利用下面公式：vl(汇点)=ve(汇点);vl(i)=Min vl(j)dut(),公式意义：由从Vi顶点指出的弧所代表的活动中取需最早开始的一个开始时间作为Vi的最迟发生时间。,由此得到下述求关键路径的算法：1）输入e条弧，建立AOE网的存储结构。2）从源点v0出发，令ve00按拓扑有序求其余各顶点的最早发生时vei（1i n-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。3）从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli(n-2 i 0)；4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。,如上所述，计算顶点的ve值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：1）在拓扑排序之前设初值，令ve(i)=0（0)ve(j),则 ve(j)=ve(i)+dut()；3）为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，则需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的 ve 值之后，从栈顶至栈底便为逆拓扑有序序列。,总之，关键路径的求解操作包括：1）计算 vej 和 vlj 向汇点递推 ve(源点)=0；ve(j)=Max ve(i)+dut()向源点递推 vl(汇点)=ve(汇点);vl(i)=Min vl(j)dut(),2）判断 l(i)=e(i)的活动（关键活动）,求最早发生时间ve的算法,Status TopologicalOrder(ALGraph G，Stack for(p=G.verticesj.firstarc；p；p=p-nextarc)k=padjvex；/对i号顶点的每个邻接点的入度减l if(-indegreek=0)Push(S，k)；/若入度减为0，入栈 if(vej+*(p-info)vek)vek=vej+*(p-info)；/for*(p-info)=dut()/while if(countG.vexnum)return ERROR；/该有向网有回路else return OK；/TopologicalOrder,求关键路径的算法,Status CriticalPath(ALGraph G)/G为有向网，输出G的各项关键活动 if(!TopologicalOrder(G，T)return ERROR；vl0.G.vexnum-1=veG.vexnum-1；/初始化顶点事件的最迟发生时间 while(!StackEmpty(T)/按拓扑逆序求各顶点的vl值 for(Pop(T,j)，p=G.verticesj.firstarc；p；p=p-nextarc)k=p-adjvex；dut=*(pinfo)；/dutif(vlk-dutnextarc)k=p-adjvex；dut=*(pinfo)；ee=vej；el=vlk-dut；tag=(ee=e1)?*:；printf(j，k，dut，ee，el，tag)；/输出关键活动/CriticalPath,例：求下图AOE网的关键路径,e(s)ve(i)l(s)vl(j)-dut(),ve(源点)=0；ve(j)=Max ve(i)+dut(),vl(汇点)=ve(汇点);vl(i)=Min vl(j)dut(),拓扑序列：V1、V3、V2、V5、V4、V6,练习：求下图AOE网的关键路径,总结：有向无环图是描述一项工程或系统的进行过程的有效工具。AOV网（顶点表示活动的有向网）与拓扑排序解决工程或系统能否顺利进行；AOE网（边表示活动的有向网）和关键路径问题估算整个工程完成所必须的最短时间，求解哪些活动为关键活动。,第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径,7.6 最短路径,所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。1.单源点最短路径 2.所有顶点对之间的最短路径,7.6.1 单源点最短路径,给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径。,V5,V0,V2,V4,V1,V3,100,30,10,60,10,20,50,5,V0,V2,V4,V3,V5,V0,始点 终点 Di 最短路径,V1V2V3V4 V5,1030100,1030100,106030100,106030100,105030100,(V0,V2)(V0,V4)(V0,V5),(V0,V2)(V0,V4)(V0,V5),(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5),(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5),(V0,V2)(V0,V4,V3)(V0,V4)(V0,V5),10503090,(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5),10503090,(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5),10503060,(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5),10503060,(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5),如何在计算机中求得最短路径？,Dijkstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：假设我们以邻接矩阵cost表示所研究的有向网。迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素Si 为 0，否则为 1。,另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为Di=costV0i，i=1n。数组D中的数据随着算法的逐步进行要不断地修改定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使Dw的值最小。于是从源点到达w只通过S中的顶点，把 w 加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离：取Dv和Dw+costwv中值较小的作为新的Dv重复上述，直到S中包含V中其余各顶点的最短路径。,V0 V1 V2 V3 V4 V5 V0 10 30 100V1 5 V2 50 V3 10 V4 20 60 V5,V0,V2,V4,V3,V5,V1,V0,V2,V4,V3,V5,V0,V2,V4,V3,V0,V2,V4,V0,V2,S=V0,V1,V5,V3,V4,V2,Vj,V5,V4,V3,V2,V1,i=5,i=4,i=3,i=2,i=1,D 终点,7.6 最短路径,7.6.1 单源点最短路径 7.6.2 所有顶点对之间的最短路径,问题描述：已知一个各边权值均大于 0 的带权有向图，对每对顶点 vivj，要求求出每一对顶点之间的最短路径和最短路径长度。解决方案：1.每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。2.形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。,弗洛伊德算法思想：假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为arcsij的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径（Vi,V0,Vj）是否存在（即判别（Vi,V0）、（V0,Vj）是否存在）。如存在，则比较（Vi,Vj）和（Vi,V0,Vj）的路径长度，取长度较短者为从 Vi到Vj 的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点 V1，依次类推。可同时求得各对顶点间的最短路径。,定义一个n阶方阵序列D(-1),D(0),D(1),D(2),D(k),D(n-1)其中：D(-1)ij=arcsij D(k)ij=Min D(k-1)ij,D(k-1)ik+D(k-1)kj 0kn-1可见，D(1)ij就是从vi到vj的中间顶点的序号不大于1的 最短路径的长度;D(k)ij就是从vi到vj的中间顶点的序号不大于k的 最短路径的长度;D(n-1)ij就是从vi到vj的最短路径的长度。,各顶点间的最短路径及其路径长度,最短路径弗洛伊德举例,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,P(2),P(1),P(0),P(-1),P,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,D(2),D(1),D(0),D(-1),D,本章小结1.熟练图的各种存储结构及构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历及算法。3.掌握以下内容：图的最小生成树和求最小生成树算法的思想;利用AOV网络的拓扑排序问题；利用AOE网络的关键路径法；带权有向图的最短路径问题。,
