《数据结构第19讲关键路径与最短路径Cppt课件》由会员分享，可在线阅读，更多相关《数据结构第19讲关键路径与最短路径Cppt课件（35页珍藏版）》请在金锄头文库上搜索。
1、第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储构造图的存储构造7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其运用有向无环图及其运用 7.5.1 7.5.1 拓扑排序拓扑排序 7.5.2 7.5.2 关键途径关键途径7.6 7.6 最短途径最短途径7.5.2 7.5.2 关键途径关键途径 对整个工程和系整个工程和系统，人，人们关关怀的是两个方面的是两个方面的的问题： 1 1工程能否工程能否顺利利进展展 对AOVAOV网网进展拓扑排序展拓扑排序 2 2估算整个工程完成所必需的最短估算整个工程完成所
2、必需的最短时间 对AOEAOE网求关网求关键途径途径AOE-AOE-网网nAOEAOE网网(Activity On Edge Network)(Activity On Edge Network)：即：即边表示活表示活动的网。的网。AOEAOE网是一个网是一个带权的有向无的有向无环图。其中：。其中：n顶点表示事件点表示事件EventEventn弧表示活弧表示活动ActivityActivityn权值表示活表示活动继续的的时间n 通常可用通常可用AOEAOE网来估算工程的完成网来估算工程的完成时间。上上图AOE-AOE-网中：网中： 共有共有1111项活活动：a1,a2,a3,a11a1,a2,a
3、3,a11； 共有共有9 9个事件：个事件：v1,v2,v3,v9v1,v2,v3,v9，每个事件表示在它之，每个事件表示在它之前的活前的活动曾曾经完成，在它之后的活完成，在它之后的活动可以开可以开场。v9表表示示整整个个工工程程的的结结束束v5表示表示a4和和a5曾经完曾经完成，成，a7和和a8可以开场可以开场与每个活动相联络的数是与每个活动相联络的数是执行该活动所需的时间执行该活动所需的时间v1表表示示整整个个工工程程的的开开始始 由于整个工程只需一个开场点和一个完成点，在正由于整个工程只需一个开场点和一个完成点，在正常的情况无环下，网中只需一个入度为零的点称常的情况无环下，网中只需一个入
4、度为零的点称作源点和一个出度为零的点称作汇点作源点和一个出度为零的点称作汇点汇汇点点源源点点根据根据AOE-AOE-网可以研讨什么问题？网可以研讨什么问题？1 1完成整完成整项工程至少需求多少工程至少需求多少时间？2 2哪些活哪些活动是影响工程是影响工程进度的关度的关键？ 完成工程的最短完成工程的最短时间是从源点到是从源点到汇点的最点的最长途径的途径的长度。途径度。途径长度最度最长的途径叫做关的途径叫做关键途径。途径。 从从v1v1到到v9v9的最的最长途径是途径是v1,v2,v5,v8,v9v1,v2,v5,v8,v9，途径，途径长度是度是1818。 假设开场点是假设开场点是v1v1，从，从
5、v1v1到到vivi的最长途径长度叫做事的最长途径长度叫做事件件vivi的最早发生时间。这个时间决议了一切以的最早发生时间。这个时间决议了一切以vivi为尾的为尾的弧所表示的活动的最早开场时间。弧所表示的活动的最早开场时间。 用用e(i)e(i)表示活动表示活动aiai的最早开场时间。的最早开场时间。V9V9的的最最早早发发生生时时间间是是1818事件事件vivi的最早发生时间的最早发生时间 l(i) l(i)e(i)e(i)两者之差意味着完成活两者之差意味着完成活动aiai的的时间余量。余量。我我们把把l(i)l(i)e(i)e(i)的活的活动叫做关叫做关键活活动。 显然，关然，关键途径上的
6、一切活途径上的一切活动都是关都是关键活活动，因此提，因此提早完成非关早完成非关键活活动并不能加快工程的并不能加快工程的进度。度。 a6a6的最早开场时间是的最早开场时间是5 5，最迟开场时间是，最迟开场时间是8 8。如。如a6a6推迟推迟3 3天开天开场或延迟场或延迟3 3天完成，都不会影响整个工程的完成。天完成，都不会影响整个工程的完成。 活动的最迟开场时间活动的最迟开场时间l(i)l(i)，这是在不推迟整个工程完，这是在不推迟整个工程完成的前提下，活动成的前提下，活动aiai最迟必需开场进展的时间。最迟必需开场进展的时间。 由此可知：区分关由此可知：区分关键活活动就是找就是找e(i)e(i
7、)l(i)l(i)的活的活动。为求得求得AOEAOE网中活网中活动的的e(i)e(i)和和l(i)l(i)，首先，首先应求得事件的最早求得事件的最早发生生时间 ve(j) ve(j)和和 最最迟发生生时间vl(j)vl(j)。 假假设活活动aiai由弧由弧表示，表示，继续时间记为dut()dut()，那么有如下关系：，那么有如下关系： 活活动i i的最早开的最早开场时间等于事件等于事件j j的最早的最早发生生时间 e(i) e(i) ve(i) ve(i) 活活动i i的最的最迟开开场时间等于事件等于事件k k的最的最迟时间减去活减去活动i i的的继续时间 l(i) l(i) vl(j) -
8、dut(i vl(j) - dut()j) 求求ve(j)ve(j)和和 vl(j) vl(j)需分两步需分两步进展：展：aiaiViViVjVjvejvej和和vljvlj可以采用下面的递推公式计算：可以采用下面的递推公式计算：1 1向汇点递推向汇点递推 ve( ve(源点源点) = 0 ) = 0 ； ve(j) = Max ve(i) + dut() ve(j) = Max ve(i) + dut()公式意公式意义：从指向：从指向顶点点VjVj的弧的活的弧的活动中取最晚完成的一中取最晚完成的一个活个活动的完成的完成时间作作为VjVj的最早的最早发生生时间vejvejp pVjVjViVi
9、2 2 向源点向源点递推推 由上一步的由上一步的递推，最后推，最后总可求出可求出汇点的最早点的最早发生生时间venven。因。因汇点就是点就是终了点，最了点，最迟发生生时间与最早与最早发生生时间一一样，即，即vln=venvln=ven。从。从汇点最点最迟发生生现时间vlnvln开开场，利用下面公式：，利用下面公式： vl( vl(汇点点) = ve() = ve(汇点点);); vl(i) = Min vl(j) dut() vl(i) = Min vl(j) dut() 公式意公式意义：由从：由从ViVi顶点指出的弧所代表的活点指出的弧所代表的活动中取需最早中取需最早开开场的一个开的一个开
10、场时间作作为ViVi的最的最迟发生生时间。 VjVjS SViVi由此得到下述求关由此得到下述求关键途径的算法：途径的算法：1 1输入入e e条弧条弧，建立，建立AOEAOE网的存网的存储构造。构造。2 2从源点从源点v0v0出出发，令，令ve0ve00 0按拓扑有序求其他按拓扑有序求其他各各顶点的最早点的最早发生生时veivei1i n-11i n-1。假。假设得到的拓扑有序序列中得到的拓扑有序序列中顶点个数小于网中点个数小于网中顶点点数数n n，那么，那么阐明网中存在明网中存在环，不能求关，不能求关键途径，途径，算法算法终止；否那么止；否那么执行步行步骤3 3。3 3从从汇点点vnvn出出
11、发，令，令vln-1= ven-1vln-1= ven-1，按逆拓，按逆拓扑有序求其他各扑有序求其他各顶点的最点的最迟发生生时间vli (n-2 vli (n-2 i 0)i 0)；4 4根据各根据各顶点的点的veve和和vlvl值，求每条弧，求每条弧s s的最早开的最早开场时间e(s)e(s)和最和最迟开开场时间l(s)l(s)。假。假设某条弧某条弧满足足条件条件e(s)=l(s)e(s)=l(s)，那么，那么为关关键活活动。 如上所述，如上所述，计算算顶点的点的veve值是在拓扑排序的是在拓扑排序的过程中程中进展的，需展的，需对拓扑排序的算法作如下修正：拓扑排序的算法作如下修正： 1 1在
12、拓扑排序之前在拓扑排序之前设初初值，令，令ve(i)=0ve(i)=00=in-10=in-1; ; 2 2在算法中添加一个在算法中添加一个计算算vivi的直接后的直接后继vjvj的的最早最早发生生时间的操作：假的操作：假设 ve(i)+dut() ve(i)+dut() ve(j), ve(j), 那么那么 ve(j) = ve(i)+dut() ve(j) = ve(i)+dut()； 3 3为了能按逆拓扑有序序列的了能按逆拓扑有序序列的顺序序计算各算各顶点的点的vlvl值，需，需记下在拓扑排序的下在拓扑排序的过程中求得的拓扑程中求得的拓扑有序序列，那么需求在拓扑排序算法中，增有序序列，那
13、么需求在拓扑排序算法中，增设一个一个栈以以记录拓扑有序序列，那么在拓扑有序序列，那么在计算求得各算求得各顶点的点的 ve ve 值之后，从之后，从栈顶至至栈底便底便为逆拓扑有序序列。逆拓扑有序序列。总之，关之，关键途径的求解操作包括：途径的求解操作包括：1 1计算算 vej vej 和和 vlj vlj 向向汇点点递推推 ve( ve(源点源点) = 0 ) = 0 ； ve(j) = Max ve(i)+ dut() ve(j) = Max ve(i)+ dut() 向源点向源点递推推 vl( vl(汇点点) = ve() = ve(汇点点);); vl(i) = Min vl(j) dut
14、() vl(i) = Min vl(j) dut()2 2判判别 l(i) = e(i) l(i) = e(i)的活的活动关关键活活动求最早发生时间求最早发生时间veve的算法的算法Status TopologicalOrder(ALGraph GStatus TopologicalOrder(ALGraph G，Stack &T)Stack &T)/有向网有向网G G采用采用邻接表，求各接表，求各顶点事件最早点事件最早发生生时间ve(ve(全局全局变量量) )/T/T为拓扑序列拓扑序列顶点点栈，s s为零入度零入度顶点点栈。 FindInDegree(G FindInDegree(G，ind
15、egree)indegree)；/对各各顶点求入度点求入度 InitStack(S) InitStack(S)； / /建零入度建零入度顶点点栈S S for(i=0 for(i=0；iG.vexnuminextarc)p=p-nextarc) k=padjvex k=padjvex； / /对i i号号顶点的每个点的每个邻接点的入度减接点的入度减l l if(-indegreek=0)Push(S if(-indegreek=0)Push(S，k)k)；/假假设入度减入度减为0 0，入，入栈 if(vej+*(p-info)vek ) vek=vej+*(p-info) if(vej+*(p
16、-info)vek ) vek=vej+*(p-info)； /for *(p-info)=dut() /for *(p-info)=dut() /while /while if(countG.vexnum) return ERRORif(countnextarc)p=p-nextarc)k=p-adjvexk=p-adjvex； dut=*(pinfo) dut=*(pinfo)； /dutj /dutkif(vlk-dutvlj) vlj=vlk-dutif(vlk-dutvlj) vlj=vlk-dut； /for /for for(j=0 for(j=0；jG.vexnumjnexta
17、rc)p=p-nextarc) k=p-adjvex k=p-adjvex； dut=*(pinfo) dut=*(pinfo)； ee=vej ee=vej；el=vlk-dutel=vlk-dut；tag = (ee=e1) ? *:tag = (ee=e1) ? *:；printf(jprintf(j，k k，dutdut，eeee，elel，tag)tag)； / /输出关出关键活活动 /CriticalPath /CriticalPath 例：求以下图例：求以下图AOEAOE网的关键途径网的关键途径v1v1v4v4v6v6v2v2v3v3v5v5a1=3a1=3a2=2a2=2a3=
18、2a3=2a6=3a6=3a4=3a4=3a7=2a7=2a8=1a8=1a5=4a5=4e(s)e(s) ve(i) ve(i)l(s)l(s) vl(j) - dut(i vl(j) - dut()j)ve(ve(源点源点) = 0 ) = 0 ；ve(j) = Max ve(i) + dut()ve(j) = Max ve(i) + dut()vl(vl(汇点点) = ve() = ve(汇点点););vl(i) = Min vl(j) dut(i, vl(i) = Min vl(j) dut()j)拓扑序列：拓扑序列：V1V1、V3V3、V2V2、V5V5、V4V4、V6V6顶点顶点v
19、evevlvl活动活动e el ll-el-ev v1 10 00 0a a1 10 01 11 1v v2 23 34 4a a2 20 00 00 0v v3 32 22 2a a3 33 34 41 1v v4 46 66 6a a4 43 34 41 1v v5 56 67 7a a5 52 22 20 0v v6 68 88 8a a6 62 25 53 3a a7 76 66 60 0a a8 86 67 71 1v1v1v4v4v6v6v2v2v3v3v5v5a1=3a1=3a2=2a2=2a3=2a3=2a6=3a6=3a4=3a4=3a7=2a7=2a8=1a8=1a5=4a
20、5=4练习：求以下图练习：求以下图AOEAOE网的关键途径网的关键途径总结：总结： 有向无环图是描画一项工程或系统的进展过程有向无环图是描画一项工程或系统的进展过程的有效工具。的有效工具。 AOV AOV网顶点表示活动的有向网与拓扑排序网顶点表示活动的有向网与拓扑排序处理工程或系统能否顺利进展；处理工程或系统能否顺利进展； AOE AOE网边表示活动的有向网和关键途径问网边表示活动的有向网和关键途径问题估算整个工程完成所必需的最短时间，求解题估算整个工程完成所必需的最短时间，求解哪些活动为关键活动。哪些活动为关键活动。第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.
21、2 图的存储构造图的存储构造7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其运用有向无环图及其运用7.6 7.6 最短途径最短途径7.6 7.6 最短途径最短途径 所谓最短途径问题是指：假设从图中某一顶所谓最短途径问题是指：假设从图中某一顶点称为源点出发到达另一顶点称为终点点称为源点出发到达另一顶点称为终点的途径能够不止一条，如何找到一条途径使得沿的途径能够不止一条，如何找到一条途径使得沿此途径上各边的权值总和到达最小。此途径上各边的权值总和到达最小。 1. 1.单源点最短途径单源点最短途径 2. 2.一切顶点对之间的最短途径一切顶点对
22、之间的最短途径7.6.1 7.6.1 单源点最短途径单源点最短途径 给定带权有向图给定带权有向图G G和源点和源点v, v, 求从求从v v到到G G中其他中其他各顶点的最短途径。各顶点的最短途径。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始点始点 终点终点 Di 最短途径最短途径V1V2V3V4 V510301001030100106030100106030100105030100(V0, V2)(V0, V4)(V0, V5)(V0, V2)(V0, V4)(V0, V5)(V0, V2)(V0, V2, V3)(V0, V4)(V0, V5)(V0,
23、 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)如何在计算机中如何在计算机中求得最短途径？求得最短途径？ Dij
24、kstra Dijkstra提出了一个按途径提出了一个按途径“长度度递增的次增的次序，逐序，逐渐得到由得到由给定源点到定源点到图的其他各点的其他各点间的最的最短途径的算法：短途径的算法：假假设我我们以以邻接矩接矩阵costcost表示所研表示所研讨的有向网。的有向网。迪杰斯特拉算法需求一个迪杰斯特拉算法需求一个顶点集合，初始点集合，初始时集合集合内只需一个源点内只需一个源点V0 V0 ，以后，以后陆续将已求得最短途径将已求得最短途径的的顶点参与到集合中，到全部点参与到集合中，到全部顶点都点都进入集合了，入集合了，过程就程就终了了。集合可用一了了。集合可用一维数数组来表示，来表示，设此此数数组为
25、S S，凡在集合，凡在集合S S以外的以外的顶点，其相点，其相应的数的数组元素元素Si Si 为 0 0 ，否那么，否那么为 1 1 。n另需一个一另需一个一维数数组D D，每个，每个顶点点对应数数组的一个的一个单元，元，记录从源点到其他各从源点到其他各顶点当前的最短途径点当前的最短途径长度，其初度，其初值为Di=costV0iDi=costV0i，i=1ni=1n。数。数组D D中的数据随着算法的中的数据随着算法的逐逐渐进展要不断地修正展要不断地修正n定定义了了S S集合和集合和D D数数组并并对其初始化后，迪杰斯特拉算法其初始化后，迪杰斯特拉算法在在进展中，都是从展中，都是从S S之外的之
26、外的顶点集合中点集合中选出一个出一个顶点点w w，使使DwDw的的值最小。于是从源点到达最小。于是从源点到达w w只只经过S S中的中的顶点，点，把把 w w 参与集合参与集合S S中，并中，并调整整D D中中记录的从源点到集合中每的从源点到集合中每个个顶点点v v的的间隔：隔：n 取取DvDv和和Dw+costwvDw+costwv中中值较小的作小的作为新的新的DvDvn反复上述，直到反复上述，直到S S中包含中包含V V中其他各中其他各顶点的最短途径。点的最短途径。 V0 V1 V2 V3 V4 V5 V0 10 30 100V1 5 V2 50 V3 10 V4 20 60 V5 V0,
27、V2,V4,V3,V5,V1V0,V2,V4,V3,V5V0,V2,V4,V3V0,V2,V4V0,V2S=V0V1V5V3V4V2VjV5V4V3V26030501060V0,4,3,530501090V0,4,53050V0,4,310100V0,530V0,460V0,2,310100V0,530V0,410V0,2V1i=5i=4i=3i=2i=1D终点终点V0V2V1V4V5V355030101010060207.6 7.6 最短途径最短途径 7.6.1 7.6.1 单源点最短途径单源点最短途径 7.6.2 7.6.2 一切顶点对之间的最短途径一切顶点对之间的最短途径问题描画：描画：
28、 知一个各知一个各边权值均大于均大于 0 0 的的带权有向有向图，对每每对顶点点 vivj vivj，要求求出每一，要求求出每一对顶点之点之间的的最短途径和最短途径最短途径和最短途径长度。度。 处理方案：理方案： 1. 1. 每次以一个每次以一个顶点点为源点，反复源点，反复执行迪杰斯行迪杰斯特拉算法特拉算法n n次。次。这样，便可求得每一，便可求得每一对顶点之点之间的的最短途径。最短途径。总的的执行行时间为O(n3)O(n3)。 2. 2. 方式更直接的弗洛伊德方式更直接的弗洛伊德FloydFloyd算法。算法。时间复复杂度也度也为O(n3)O(n3)。弗洛伊德算法思想：弗洛伊德算法思想： 假
29、假设求从求从顶点点ViVi到到VjVj的最短途径。假的最短途径。假设从从ViVi到到VjVj有弧，那么从有弧，那么从ViVi到到VjVj存在一条存在一条长度度为arcsijarcsij的途径，的途径，该途径不一定是最短途径，途径不一定是最短途径，尚需尚需进展展n n次次试探。探。 首先思索途径首先思索途径Vi,V0,VjVi,V0,Vj能否存在即判能否存在即判别Vi,V0Vi,V0、V0,VjV0,Vj能否存在。如存在，能否存在。如存在，那么比那么比较Vi,VjVi,Vj和和Vi,V0,VjVi,V0,Vj的途径的途径长度，度，取取长度度较短者短者为从从 Vi Vi到到Vj Vj 的中的中间顶
30、点的序号不点的序号不大于大于0 0 的最短途径。假的最短途径。假设在途径上再添加一个在途径上再添加一个顶点点 V1 V1，依次依次类推。可同推。可同时求得各求得各对顶点点间的最的最短途径。短途径。定定义一个一个n n阶方方阵序列序列D(-1),D(0),D(1),D(2),D(k),D(n-1)D(-1),D(0),D(1),D(2),D(k),D(n-1)其中：其中： D(-1)ij= arcsij D(-1)ij= arcsij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k- D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 1)kj
31、0kn-1 0kn-1可可见，D(1)ijD(1)ij就是从就是从vivi到到vjvj的中的中间顶点的序号不大于点的序号不大于1 1的的 最短途径的最短途径的长度度; ; D(k)ij D(k)ij就是从就是从vivi到到vjvj的中的中间顶点的序号不大于点的序号不大于k k的的 最短途径的最短途径的长度度; ; D(n-1)ij D(n-1)ij就是从就是从vivi到到vjvj的最短途径的的最短途径的长度。度。0 4 116 0 23 0 各各顶顶点点间间的最短途径及其途的最短途径及其途径径长长度度 最短途径弗洛伊德最短途径弗洛伊德举举例例 0 4 116 0 23 021CABCABCBC
32、AABCABCABCABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400 320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB本章小结本章小结1.1.熟熟练练图图的的各各种种存存储储构构造造及及构构造造算算法法，了了解解实实践践问问题题的的求求解解效效率率与与采采用用何何种种存存储储构构造造和和算算法法有有亲亲密密联络。联络。2.2.熟练掌握图的两种搜索途径的遍历及算法。熟练掌握图的两种搜索途径的遍历及算法。3.3.掌握以下内容：掌握以下内容： 图的最小生成树和求最小生成树算法的思想图的最小生成树和求最小生成树算法的思想; ; 利用利用AOVAOV网络的拓扑排序问题；网络的拓扑排序问题； 利用利用AOEAOE网络的关键途径法；网络的关键途径法； 带权有向图的最短途径问题。带权有向图的最短途径问题。
