数据结构第19讲关键路径与最短路径课件.ppt
35页
第第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）估算整个工程完成所必须的最短时间）估算整个工程完成所必须的最短时间 对对AOEAOE网求关键路径网求关键路径 AOE-AOE-网网nAOEAOE－网－网(Activity On Edge Network)(Activity On Edge Network)：即边：即边表示活动的网表示活动的网AOEAOE网是一个带权的有向无环网是一个带权的有向无环图。
其中：图其中：n顶点表示事件（顶点表示事件（EventEvent））n弧表示活动（弧表示活动（ActivityActivity））n权值表示活动持续的时间权值表示活动持续的时间 通常可用通常可用AOEAOE网来估算工程的完成时间网来估算工程的完成时间 上图上图AOE-AOE-网中：网中： 共有共有1111项活动：项活动：a a1 1,a,a2 2,a,a3 3,…a,…a1111；； 共有共有9 9个事件：个事件：v v1 1,v,v2 2,v,v3 3,…v,…v9 9，每个事件表示在它之前，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始的活动已经完成，在它之后的活动可以开始v9表表示示整整个个工工程程的的结结束束v5表示表示a4和和a5已经完已经完成，成， a7和和a8可以开始可以开始与每个活动相联系的数是与每个活动相联系的数是执行该活动所需的时间执行该活动所需的时间v1表表示示整整个个工工程程的的开开始始 由于整个工程只有一个开始点和一个完成点，在正由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只有一个入度为零的点（称常的情况（无环）下，网中只有一个入度为零的点（称作作源点源点）和一个出度为零的点（称作）和一个出度为零的点（称作汇点汇点））汇汇点点源源点点 依据依据AOE-AOE-网可以研究什么问题？网可以研究什么问题？（（1 1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？（（2 2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？ 完成工程的最短时间是从源点到汇点的完成工程的最短时间是从源点到汇点的最长路径最长路径的的长度。
路径长度最长的路径叫做长度路径长度最长的路径叫做关键路径关键路径 从从v v1 1到到v v9 9的最长路径是（的最长路径是（v v1 1,v,v2 2,v,v5 5,v,v8 8,v,v9 9），路径长），路径长度是度是1818 假设开始点是假设开始点是v v1 1，从，从v v1 1到到v vi i的最长路径长度叫做的最长路径长度叫做事事件件v vi i的最早发生时间的最早发生时间这个时间决定了所有以这个时间决定了所有以v vi i为尾的为尾的弧所表示的活动的最早开始时间弧所表示的活动的最早开始时间 用用e(i)e(i)表示活动表示活动a ai i的最早开始时间的最早开始时间V V9 9的的最最早早发发生生时时间间是是1818事件事件v vi i的最早发生时间的最早发生时间 l(i) l(i)－－e(i)e(i)两者之差意味着完成活动两者之差意味着完成活动a ai i的时间余量的时间余量我们把我们把l(i)l(i)＝＝e(i)e(i)的活动叫做关键活动的活动叫做关键活动 显然，关键路径上的所有活动都是关键活动，因此提显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。
前完成非关键活动并不能加快工程的进度 a a6 6的最早开始时间是的最早开始时间是5 5，最迟开始时间是，最迟开始时间是8 8如a a6 6推迟推迟3 3天开天开始或延迟始或延迟3 3天完成，都不会影响整个工程的完成天完成，都不会影响整个工程的完成 活动的最迟开始时间活动的最迟开始时间l(i)l(i)，这是在不推迟整个工程完，这是在不推迟整个工程完成的前提下，活动成的前提下，活动a ai i最迟必须开始进行的时间最迟必须开始进行的时间 由此可知：辨别关键活动就是找由此可知：辨别关键活动就是找e(i)e(i)＝＝l(i)l(i)的活动为求得为求得AOEAOE网中活动的网中活动的e(i)e(i)和和l(i)l(i)，首先应求得事件的最早，首先应求得事件的最早发生时间发生时间 ve(j) ve(j)和和 最迟发生时间最迟发生时间vl(j)vl(j) 若活动若活动a ai i由弧由弧
因汇点就是结束点，最迟发生时间与最早发生因汇点就是结束点，最迟发生时间与最早发生时间相同，即时间相同，即vl[n]=ve[n]vl[n]=ve[n]从汇点最迟发生现时间从汇点最迟发生现时间vl[n]vl[n]开始，利用下面公式：开始，利用下面公式： vl( vl(汇点汇点) = ve() = ve(汇点汇点);); vl(i) = Min{ vl(j) – dut(
如果得到的拓扑有序）如果得到的拓扑有序序列中顶点个数小于网中顶点数序列中顶点个数小于网中顶点数n n，则说明网中存在环，，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（不能求关键路径，算法终止；否则执行步骤（3 3）3 3）从汇点）从汇点v vn n出发，令出发，令vl[n-1]= ve[n-1]vl[n-1]= ve[n-1]，按逆拓扑有序，按逆拓扑有序求求其余各顶点的最迟发生时间其余各顶点的最迟发生时间vl[i]vl[i] (n-2 ≥i≥ 0)(n-2 ≥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）在拓扑排序之前设初值，令）在拓扑排序之前设初值，令ve(i)=0ve(i)=0（（0<=i
序列 总之，关键路径的求解操作包括：总之，关键路径的求解操作包括：1 1）计算）计算 ve[j] ve[j] 和和 vl[j] vl[j] ①① 向汇点递推向汇点递推 ve( ve(源点源点) = 0 ) = 0 ；； ve(j) = Max { ve(i)+ dut(
为零入度顶点栈 FindInDegree(G FindInDegree(G，，indegree)indegree)；；////对各顶点求入度对各顶点求入度 InitStack(S) InitStack(S)；； ////建零入度顶点栈建零入度顶点栈S S for(i=0 for(i=0；；i
的有效工具 AOV AOV网（顶点表示活动的有向网）与拓扑排序网（顶点表示活动的有向网）与拓扑排序－－解决工程或系统能否顺利进行；－－解决工程或系统能否顺利进行； AOE AOE网（边表示活动的有向网）和关键路径问网（边表示活动的有向网）和关键路径问题－－估算整个工程完成所必须的最短时间，求解题－－估算整个工程完成所必须的最短时间，求解哪些活动为关键活动哪些活动为关键活动 第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.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.所有顶点对之间的最短路径所有顶点对之间的最短路径 7.6.1 7.6.1 单源点最短路径单源点最短路径 给定带权有向图给定带权有向图G G和源点和源点v, v, 求从求从v v到到G G中其余中其余各顶点的最短路径各顶点的最短路径V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始点始点 终点终点 D[i] 最短路径最短路径V1V2V3V4 V5∞10∞30100∞10∞30100∞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 Dijkstra提出了一个按路径提出了一个按路径““长度长度””递增的递增的次序，逐步得到由给定源点到图的其余各点间的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：最短路径的算法：n假设我们以邻接矩阵假设我们以邻接矩阵costcost表示所研究的有向网。
表示所研究的有向网n迪杰斯特拉算法需要一个顶点集合，初始时集合内迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点只有一个源点V V0 0 ，，以后陆续将已求得最短路径的顶以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程点加入到集合中，到全部顶点都进入集合了，过程就结束了集合可用一维数组来表示，设此数组为就结束了集合可用一维数组来表示，设此数组为S S，，凡在集合凡在集合S S以外的顶点，其相应的数组元素以外的顶点，其相应的数组元素S[i] S[i] 为为 0 0 ，否则为，否则为 1 1 n另需一个一维数组另需一个一维数组D D，每个顶点对应数组的一个单元，记，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为录从源点到其他各顶点当前的最短路径长度，其初值为D[iD[i]=cost]=cost[V[V0 0][i]][i]，，i=1…ni=1…n数组数组D D中的数据随着算法的逐步进行中的数据随着算法的逐步进行要不断地修改要不断地修改n定义了定义了S S集合和集合和D D数组并对其初始化后，迪杰斯特拉算法数组并对其初始化后，迪杰斯特拉算法在进行中，都是从在进行中，都是从S S之外的顶点集合中选出一个顶点之外的顶点集合中选出一个顶点w w，，使使D[wD[w] ]的值最小。
于是从源点到达的值最小于是从源点到达w w只通过只通过S S中的顶点，中的顶点，把把 w w 加入集合加入集合S S中，并调整中，并调整D D中记录的从源点到集合中每中记录的从源点到集合中每个顶点个顶点v v的距离：的距离： 取取D[vD[v] ]和和D[w]+cost[w][vD[w]+cost[w][v] ]中值较小的作为新的中值较小的作为新的D[vD[v] ]n重复上述，直到重复上述，直到S S中包含中包含V V中其余各顶点的最短路径中其余各顶点的最短路径 V0 V1 V2 V3 V4 V5 V0 ∞ ∞ 10 ∞ 30 100V1 ∞ ∞ 5 ∞ ∞ ∞ V2 ∞ ∞ ∞ 50 ∞ ∞ V3 ∞ ∞ ∞ ∞ ∞ 10 V4 ∞ ∞ ∞ 20 ∞ 60 V5 ∞ ∞ ∞ ∞ ∞ ∞ {V0 0,V2 2,V4 4,V3 3,V5 5 ,V1 1}{V0 0,V2 2,V4 4,V3 3,V5 5}{V0 0,V2 2,V4 4,V3 3}{V0 0,V2 2,V4 4}{V0 0,V2 2}S={V0 0}V1 1V5 5V3 3V4 4V2 2Vj jV5 5V4 4V3 3V2 260305010∞∞60{V0,4,3,5}305010∞∞90{V0,4,5}3050{V0,4,3}10∞∞100{V0,5}30{V0,4}60{V0,2,3}10∞∞100{V0,5}30{V0,4}∞∞10{V0,2}∞∞V1 1i=5i=4i=3i=2i=1 D 终点终点V0V2V1V4V5V35503010101006020 7.6 7.6 最短路径最短路径 7.6.1 7.6.1 单源点最短路径单源点最短路径 7.6.2 7.6.2 所有顶点对之间的最短路径所有顶点对之间的最短路径 问题描述：问题描述： 已知一个各边权值均大于已知一个各边权值均大于 0 0 的带权有向图，的带权有向图，对每对顶点对每对顶点 vi≠vj vi≠vj，要求求出每一对顶点之间的，要求求出每一对顶点之间的最短路径和最短路径长度。
最短路径和最短路径长度 解决方案：解决方案： 1. 1. 每次以一个顶点为源点，重复执行迪杰斯每次以一个顶点为源点，重复执行迪杰斯特拉算法特拉算法n n次这样，便可求得每一对顶点之间的次这样，便可求得每一对顶点之间的最短路径总的执行时间为最短路径总的执行时间为O(nO(n3 3) ) 2. 2. 形式更直接的弗洛伊德（形式更直接的弗洛伊德（FloydFloyd）算法时间复杂度也为时间复杂度也为O(nO(n3 3) ) 弗洛伊德算法思想：弗洛伊德算法思想： 假设求从顶点假设求从顶点V Vi i到到V Vj j的最短路径如果从的最短路径如果从V Vi i到到V Vj j有弧，则从有弧，则从V Vi i到到V Vj j存在一条长度为存在一条长度为arcs[i][j]arcs[i][j]的的路径，该路径不一定是最短路径，尚需进行路径，该路径不一定是最短路径，尚需进行n n次试次试探 首先考虑路径（首先考虑路径（V Vi i,V,V0 0,V,Vj j）是否存在（即判别）是否存在（即判别（（V Vi i,V,V0 0）、（）、（V V0 0,V,Vj j）是否存在）。
如存在，则比）是否存在）如存在，则比较（较（V Vi i,V,Vj j）和（）和（V Vi i,V,V0 0,V,Vj j）的路径长度，取长度较）的路径长度，取长度较短者为从短者为从 V Vi i到到V Vj j 的中间顶点的序号不大于的中间顶点的序号不大于0 0 的最的最短路径假如在路径上再增加一个顶点短路径假如在路径上再增加一个顶点 V V1 1，，……依依次类推可同时求得各对顶点间的最短路径可同时求得各对顶点间的最短路径 定义一个定义一个n n阶方阵序列阶方阵序列D D(-1)(-1),D,D(0)(0),D,D(1)(1),D,D(2)(2),…,D,…,D(k)(k),…,D,…,D(n-1)(n-1)其中：其中： D D(-1)(-1)[i][j]= arcs[i][j][i][j]= arcs[i][j] D D(k)(k)[i][j]=Min { D[i][j]=Min { D(k-1)(k-1)[i][j], D[i][j], D(k-1)(k-1)[i][k]+ D[i][k]+ D(k-1)(k-1)[k][j] }[k][j] } 0≤k≤n-10≤k≤n-1可见，可见，D D(1)(1)[i][j][i][j]就是从就是从v vi i到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于1 1的的 最短路径的长度最短路径的长度; ; D D(k)(k)[i][j][i][j]就是从就是从v vi i到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于k k的的 最短路径的长度最短路径的长度; ; D D(n-1)(n-1)[i][j][i][j]就是从就是从v vi i到到v vj j的最短路径的长度。
的最短路径的长度0 4 116 0 23 ∞ 0 各顶点间的最短路径及其路径长度各顶点间的最短路径及其路径长度 最短路径弗洛伊德举例最短路径弗洛伊德举例 0 4 116 0 23 ∞ 021CABCABCBCAABCABCABCABCBAABCABCABCABCBAACAB0210210210210P(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网络的关键路径法；网络的关键路径法； 带权有向图的最短路径问题。
带权有向图的最短路径问题。
