7_2图(拓扑排序、关键路径、最短路径).ppt

0 1 2 4 5 3 17 4 10 4 5 20 11 4 13 6 12 9 14 21 18/4 5/0 13/1 12/0 9/4 已知弧上带权值的有向图，计算从V0到其他各顶点的最短路径。 1 2 3 4 5 shortest 9 18 12 5 13 path 4 4 0 0 1 已求出最短路径的顶点集合为： 0,4,1,3,5 未求出最短路径的顶点剩下2，而5没有到2的弧，所以不做修正 0 1 2 4 5 3 17 4 10 4 5 20 11 4 13 6 12 9 14 21 18/4 5/0 13/1 12/0 9/4 已知弧上带权值的有向图，计算从V0到其他各顶点的最短路径。 1 2 3 4 5 shortest 9 18 12 5 13 path 4 4 0 0 1 已求出最短路径的顶点集合为： 0,4,1,3,5,2 结束 0 1 2 4 5 3 17 4 10 4 5 20 11 4 13 6 12 9 14 21 18/4 5/0 13/1 12/0 9/4 已知弧上带权值的有向图，计算从V0到其他各顶点的最短路径。 0-4-1 0-4-2 0-3 0-4 0-4-1-5 1 2 3 4 5 shortest 9 18 12 5 13 path 4 4 0 0 1 五、最短路径 任两点间最短路径问题 五、最短路径 Floyd算法 算法思想 定义P(i,j,k)为：从vi到vj，由序号不大于k的顶点为中间点（或直达）可构成的最短路径。 五、最短路径 Floyd算法 算法思想 P(i,j,0) P(i,j,k) 五、最短路径 Floyd算法 算法思想 E1：初始化从vi到vj的目前已知较短路径为从vi到vj的直达弧； E2：对每两顶点对(vi,vj)依次计算P(i,j,k)，k=0…n-1，计算规则为：P(i,j,k) = min( P(i,k,k-1)+P(k,j,k-1), P(i,j,k-1) ) 0 1 2 4 5 3 17 4 10 4 5 20 11 4 13 6 12 9 14 21 已知弧上带权值的有向图，计算每两个顶点间的最短路径。 第 七 章 图 第七章 图(拓扑排序、关键路 径、最短路径) 四、有向无环图 有向无环图 概念 四、有向无环图 拓扑排序 拓扑排序的概念 四、有向无环图 拓扑排序 拓扑排序算法 E1：计算各顶点的入度； E2：将入度为0的顶点入栈； E3：循环直到栈空： E31：从栈中弹出一个顶点，输出到拓扑序中； E32：将该顶点的所有邻接点的入度减1，若某个邻接点的入度减为0，则将该邻接点入栈； 入度indegree[] 栈（顶-底） 输出 v1 v2 v3 v4 v5 v6 0 2 2 1 0 3 v5,v1 0 2 1 1 0 2 v1 v5 0 1 0 0 0 2 v4,v3 v5,v1 0 0 0 0 0 1 v2,v3 v5,v1,v4 0 0 0 0 0 1 v3 v5,v1,v4,v2 0 0 0 0 0 0 v6 v5,v1,v4,v2,v3 v5,v1,v4,v2,v3,v6 四、有向无环图 关键路径 关键路径的概念及意义 四、有向无环图 关键路径 关键路径的计算 E1：依拓扑序计算各顶点的最早发生时间ve； E2：依逆拓扑序计算各顶点的最迟发生时间vl； E3：计算每条弧的最早开始时间e和最迟开始时间l，若e等于l，则输出该弧（关键弧）； 四、有向无环图 关键路径 关键路径的计算 最早发生时间ve的计算 初值的选择 ve[k]=max{ ve[i] + w[i][k] | vi,vk∈E } 四、有向无环图 关键路径 关键路径的计算 最迟发生时间 vl的计算 初值的选择 vl[i]=min{ vl[j]-w[i][j] | vi,vj∈E } 四、有向无环图 关键路径 关键路径的计算 弧的最早开始时间和e和最迟开始时间l的计算 eij = ve[i] lij = vl[j]-w[i][j] 0/ 0/ 0/ 0/ 0/ 0/ 0/ 0/ 0/ 0/ 0/ 0/ 5/ 0/ 24/ 41/ 15/ 3/ 21/ 18/ 28/ 41/ 50/ 62/ 5/62 0/62 24/62 41/62 15/62 3/62 21/62 18/62 28/62 41/62 50/62 62/62 5/5 0/0 24/24 41/41 15/15 3/9 21/27 18/19 28/29 41/47 50/50 62/62 5/5 0/0 24/24 41/41 15/15 3/9 21/27 18/19 28/29 41/47 50/50 62/62 0/0 0/6 5/12 5/5 3/11 3/9