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

《数据结构第19讲关键路径与最短路径C》由会员分享，可在线阅读，更多相关《数据结构第19讲关键路径与最短路径C（35页珍藏版）》请在装配图网上搜索。

1、第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,）,,弧表示活动（,Activi

2、ty,）,,权值表示活动持续的时间,,,通常可用,AOE,网来估算工程的完成时间。,上图AOE-网中：,,共有11项活动：a,1,,a,2,,a,3,,…a,11,；,,共有9个事件：v,1,,v,2,,v,3,,…v,9,，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。,v,9,,表,,示,,整,,个,,工,,程,,的,,结,,束,v,5,表示a,4,和a,5,已经完,,成， a,7,和a,8,可以开始,与每个活动相联系的数是执行该活动所需的时间,v,1,,表,,示,,整,,个,,工,,程,,的,,开,,始,由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只

3、有一个入度为零的点（称作,源点,）和一个出度为零的点（称作,汇点,）,汇点,源点,依据AOE-网可以研究什么问题？,（1）完成整项工程至少需要多少时间？,,,（2）哪些活动是影响工程进度的关键？,完成工程的最短时间是从源点到汇点的,最长路径,的长度。路径长度最长的路径叫做,关键路径,。,,从v,1,到v,9,的最长路径是（v,1,,v,2,,v,5,,v,8,,v,9,），路径长度是18。,假设开始点是v,1,，从v,1,到v,i,的最长路径长度叫做,事件v,i,的最早发生时间,。这个时间决定了所有以v,i,为尾的弧所表示的活动的最早开始时间。,,用,e(i)表示活动a,i,的最早开始时间,。

4、,V,9,的最早发生时间是18,事件v,i,的最早发生时间,l(i)－e(i)两者之差意味着完成活动a,i,的时间余量。我们把,l(i)＝e(i)的活动叫做关键活动,。,,显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。,a,6,的最早开始时间是5，最迟开始时间是8。如a,6,推迟3天开始或延迟3天完成，都不会影响整个工程的完成。,活动的最迟开始时间,l(i)，这是在不推迟整个工程完成的前提下，活动a,i,最迟必须开始进行的时间。,由此可知：辨别关键活动就是找e(i)＝l(i)的活动。为求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早发生时间 v

5、e(j)和 最迟发生时间vl(j)。,,若活动a,i,由弧表示，持续时间记为dut()，则有如下关系：,,,,活动i的最早开始时间等于事件j的最早发生时间,,e(i)＝ ve(i),,活动i的最迟开始时间等于事件k的最迟时间减去活动i的持续时间,,l(i)＝ vl(j) - dut(),,求ve(j)和 vl(j)需分两步进行：,a,i,V,i,V,j,ve[j]和vl[j]可以采用下面的递推公式计算：,,（1）向汇点递推,,ve(源点) = 0 ；,,ve(j) = Max{ ve(i) + dut()},公式意义：从指向顶点V,j,的弧的活动中取,最晚,完成的一个活动的完成时间作为V,j,

6、的最早发生时间ve[j],p,V,j,V,i,（2） 向源点递推,,由上一步的递推，最后总可求出汇点的最早发生时间ve[n]。因汇点就是结束点，最迟发生时间与最早发生时间相同，即vl[n]=ve[n]。从汇点最迟发生现时间vl[n]开始，利用下面公式：,,,,vl(汇点) = ve(汇点);,,vl(i) = Min{ vl(j) – dut() },公式意义：由从V,i,顶点指出的弧所代表的活动中取需,最早,开始的一个开始时间作为V,i,的最迟,发生,时间。,V,j,S,V,i,由此得到下述求关键路径的算法：,,1）输入e条弧，建立AOE网的存储结构。,,2）从源点v,0,出发，令ve[0]

7、＝0按拓扑有序求其余,各顶点的最早发生时ve[i],（1≤i≤ n-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。,,3）从汇点v,n,出发，令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

8、)=0（0<=i ve(j), 则 ve(j) = ve(i)+dut()；,,3）为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，则需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的 ve 值之后，从栈顶至栈底便为逆拓扑有序序列。,总之，关键路径的求解操作包括：,,1）计算 ve[j] 和 vl[j],,,,①,向汇点递推,,ve(源点) = 0 ；,,ve(j) = Max { ve(i)+ dut()},,

9、,②,向源点递推,,vl(汇点) = ve(汇点);,,vl(i) = Min { vl(j) – dut()},2）判断 l(i) = e(i)的活动（关键活动）,求最早发生时间ve的算法,Status TopologicalOrder(ALGraph G，Stack &T){,,//有向网G采用邻接表，求各顶点事件最早发生时间ve(全局变量),,//T为拓扑序列顶点栈，s为零入度顶点栈。,,FindInDegree(G，indegree)；,//对各顶点求入度,,InitStack(S)；,//建零入度顶点栈S,,for(i=0；i

10、[i])Push(S，i),//入度为0者进栈,,count=0；,,,InitStack(T)； ve[0..G.vexnum-1]=0；,,//初始化,,,while(!StackEmpty(S)){,,Pop(S，j)；,Push(T，j)；,++count;,,for(p=G.vertices[j].firstarc；p；p=p->nextarc){,,k=p—>adjvex；,//对i号顶点的每个邻接点的入度减l,,if(--indegree[k]==0)Push(S，k)；,//若入度减为0，入栈,,,if(ve[j]+*(p->info)>ve[k] ) ve[k]=ve[j]+

11、*(p->info)；,,},//for *(p->info)=dut(),,},//while,,,if(count

12、ckEmpty(T)),//按拓扑逆序求各顶点的vl值,,for(Pop(T,j)，p=G.vertices[j].firstarc；p；p=p->nextarc){,,k=p->adjvex； dut=*(p—>info)；,//dut,,if(vl[k]-dutnextarc){,,k=p->adjvex； dut=*(p—>info)；,,ee=ve[j]；el=vl[k]-dut；tag

13、 = (ee==e1) ? ‘*’:’’；,,printf(j，k，dut，ee，el，tag)；,//输出关键活动,},,},//CriticalPath,,例：,求下图AOE网的关键路径,v,1,v,4,v,6,v,2,v,3,v,5,a,1,=3,a,2,=2,a,3,=2,a,6,=3,a,4,=3,a,7,=2,a,8,=1,a,5,=4,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()},拓扑

14、序列：V1、V3、V2、V5、V4、V6,顶点,ve,vl,活动,e,l,l-e,v,1,0,0,a,1,0,1,1,v,2,3,4,a,2,0,0,0,v,3,2,2,a,3,3,4,1,v,4,6,6,a,4,3,4,1,v,5,6,7,a,5,2,2,0,v,6,8,8,a,6,2,5,3,,,,a,7,6,6,0,,,,a,8,6,7,1,v,1,v,4,v,6,v,2,v,3,v,5,a,1,=3,a,2,=2,a,3,=2,a,6,=3,a,4,=3,a,7,=2,a,8,=1,a,5,=4,练习：求下图AOE网的关键路径,总结：,,有向无环图是描述一项工程或系统的进行过程的有效工

15、具。,,AOV网（顶点表示活动的有向网）与拓扑排序－－解决工程或系统能否顺利进行；,,AOE网（边表示活动的有向网）和关键路径问题－－估算整个工程完成所必须的最短时间，求解哪些活动为关键活动。,第7章 图,,,7.1 图的定义和术语,,7.2 图的存储结构,,7.3 图的遍历,,7.4 图的连通性问题,,7.5 有向无环图及其应用,,7.6 最短路径,7.6 最短路径,所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。,,,,1.单源点最短路径,,2.所有顶点对之间的最短路径,7.6.1

16、单源点最短路径,给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。,V,5,V,0,V,2,V,4,V,1,V,3,100,30,10,60,10,20,50,5,V,0,V,2,V,4,V,3,V,5,V,0,始点 终点 D[i] 最短路径,V,1,,V,2,,V,3,,V,4,V,5,∞,,10,,∞,,30,,100,∞,,10,,∞,,30,,100,∞,,10,,60,,30,,100,∞,,10,,60,,30,,100,∞,,10,,50,,30,,100,,(V,0,, V,2,),,,(V,0,, V,4,),,(V,0,, V,5,),,(V

17、,0,, V,2,),,,(V,0,, V,4,),,(V,0,, V,5,),,(V,0,, V,2,),,(V,0,, V,2,, V,3,),,(V,0,, V,4,),,(V,0,, V,5,),,(V,0,, V,2,),,(V,0,, V,2,, V,3,),,(V,0,, V,4,),,(V,0,, V,5,),,(V,0,, V,2,),,(V,0,, V,4,, V,3,),,(V,0,, V,4,),,(V,0,, V,5,),∞,,10,,50,,30,,90,,(V,0,, V,2,),,(V,0,, V,4,, V,3,),,(V,0,, V,4,),,(V,0,,

18、V,4,, V,5,),∞,,10,,50,,30,,90,,(V,0,, V,2,),,(V,0,, V,4,, V,3,),,(V,0,, V,4,),,(V,0,, V,4,, V,5,),∞,,10,,50,,30,,60,,(V,0,, V,2,),,(V,0,, V,4,, V,3,),,(V,0,, V,4,),,(V,0,, V,4,, V,3,, V,5,),∞,,10,,50,,30,,60,,(V,0,, V,2,),,(V,0,, V,4,, V,3,),,(V,0,, V,4,),,(V,0,, V,4,, V,3,, V,5,),如何在计算机中求得最短路径？,Dij

19、kstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：,,假设我们以邻接矩阵,cost,表示所研究的有向网。,,迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点,V,0,,，,以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为,S,，,凡在集合,S,以外的顶点，其相应的数组元素,S[i],为,0,，否则为,1,。,另需一个一维数组,D,，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为,D[i,]=cost[V,0,][i],，,i=1…n,。,数

20、组,D,中的数据随着算法的逐步进行要不断地修改,,定义了,S,集合和,D,数组并对其初始化后，迪杰斯特拉算法在进行中，都是从,S,之外的顶点集合中选出一个顶点,w,，,使,D[w,],的值最小。于是从源点到达,w,只通过,S,中的顶点，把,w,加入集合,S,中，并调整,D,中记录的从源点到集合中每个顶点,v,的距离：,,取,D[v,],和,D[w]+cost[w][v,],中值较小的作为新的,D[v,],,重复上述，直到,S,中包含,V,中其余各顶点的最短路径。,V,0,V,1,V,2,V,3,V,4,V,5,,,V,0,∞ ∞ 10 ∞ 30 100,,V,1,∞ ∞ 5

21、 ∞ ∞ ∞,,V,2,∞ ∞ ∞ 50 ∞ ∞,,V,3,∞ ∞ ∞ ∞ ∞ 10,,V,4,∞ ∞ ∞ 20 ∞ 60,,V,5,∞ ∞ ∞ ∞ ∞ ∞,{V,0,,V,2,,V,4,,V,3,,V,5,,V,1,},{V,0,,V,2,,V,4,,V,3,,V,5,},{V,0,,V,2,,V,4,,V,3,},{V,0,,V,2,,V,4,},{V,0,,V,2,},S={V,0,},V,1,V,5,V,3,V,4,V,2,V,j,V,5,V,4,V,3,V,2,60,30,50,10,∞,60{V,0,4,3,5,},30,50,1

22、0,∞,90{V,0,4,5,},30,50{V,0,4,3,},10,∞,100{V,0,5,},30{V,0,4,},60{V,0,2,3,},10,∞,100{V,0,5,},30{V,0,4,},∞,10{V,0,2,},∞,V,1,i=5,i=4,i=3,i=2,i=1,D,,终点,V,0,V,2,V,1,V,4,V,5,V,3,5,50,30,10,10,100,60,20,7.6 最短路径,7.6.1 单源点最短路径,,,7.6.2 所有顶点对之间的最短路径,问题描述：,,已知一个各边权值均大于 0 的带权有向图，对每对顶点 vi≠vj，要求求出每一对顶点之间的最短路径和最短路径

23、长度。,,解决方案：,,1. 每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n,3,)。,,2. 形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n,3,)。,弗洛伊德算法思想：,,假设求从顶点V,i,到V,j,的最短路径。如果从V,i,到V,j,有弧，则从V,i,到V,j,存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。,,首先考虑路径（V,i,,V,0,,V,j,）是否存在（即判别（V,i,,V,0,）、（V,0,,V,j,）是否存在）。如存在，则比较（V,i,,V,j,）和（V,i

24、,,V,0,,V,j,）的路径长度，取长度较短者为从 V,i,到V,j,的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点 V,1,，…依次类推。可同时求得各对顶点间的最短路径。,定义一个n阶方阵序列,,D,(-1),,D,(0),,D,(1),,D,(2),,…,D,(k),,…,D,(n-1),,其中：,,D,(-1),[i][j]= arcs[i][j],,D,(k),[i][j]=Min { D,(k-1),[i][j], D,(k-1),[i][k]+ D,(k-1),[k][j] },,,0≤k≤n-1,,可见，D,(1),[i][j]就是从v,i,到v,j,的中间顶

25、点的序号不大于1的,,最短路径的长度;,,D,(k),[i][j]就是从v,i,到v,j,的中间顶点的序号不大于k的,,最短路径的长度;,,D,(n-1),[i][j]就是从v,i,到v,j,的最短路径的长度。,0 4 11,,6 0 2,,3,∞,0,,各顶点间的最短路径及其路径长度,,,最短路径弗洛伊德举例,,0 4 11,,6 0 2,,3,∞,0,2,1,,CAB,CA,BC,,BCA,ABC,AB,,,CAB,CA,BC,,BA,ABC,AB,,,CAB,CA,BC,,BA,AC,AB,,0,2,1,0,2,1,0,2,1,0,2,

26、1,0,P,(2),P,(1),P,(0),P,(-1),P,2,1,0,7,3,2,0,5,6,4,0,0,7,3,2,0,6,6,4,0,0,7,3,2,0,6,11,4,0,0,,3,2,0,6,11,4,0,0,2,1,0,2,1,0,2,1,0,2,1,0,D,(2),D,(1),D,(0),D,(-1),D,,,CA,BC,,BA,AC,AB,,本章小结,,1.熟练图的各种存储结构及构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。,,2,.,熟练掌握图的两种搜索路径的遍历及算法。,,3,.掌握以下内容：,,图的最小生成树和求最小生成树算法的思想;,,利用AOV网络的拓扑排序问题；,,利用AOE网络的关键路径法；,,带权有向图的最短路径问题。,