第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-网nAOE网(Activity On Edge Network)：即边 表示活动的网。AOE网是一个带权的有向无环图 。其中：n顶点表示事件（Event）n弧表示活动（Activity）n权值表示活动持续的时间通常可用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)需分两步进行：ai ViVjvej和vlj可以采用下面的递推公式计算：（1）向汇点递推ve(源点) = 0 ；ve(j) = Max ve(i) + dut()公式意义：从指向顶点Vj的弧的活动中取最晚完成的一个 活动的完成时间作为Vj的最早发生时间vejpVjVi（2） 向源点递推由上一步的递推，最后总可求出汇点的最早发生时间ven。因汇点就是结束点，最迟发生时间与最早发生时间相同，即vln=ven。从汇点最迟发生现时间vln开始，利用下面公式：vl(汇点) = ve(汇点);vl(i) = Min vl(j) dut() 公式意义：由从Vi顶点指出的弧所代表的活动中取需最早 开始的一个开始时间作为Vi的最迟发生时间。 VjSVi由此得到下述求关键路径的算法：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 vl(i) = Min vl(j) dut()拓扑序列：V1、V3、V2、V5、V4、V6顶点vevl活动ell-e v100a1011 v234a2000 v322a3341 v466a4341 v567a5220 v688a6253 a7660a8671v1v4v6v2v3v5a1=3a2=2a3=2a6=3a4=3a7=2a8=1a5=4练习：求下图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中其余 各顶点的最短路径。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, 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提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：n假设我们以邻接矩阵cost表示所研究的有向网。n迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0 ，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素Si 为 0 ，否则为 1 。n另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为Di=costV0i，i=1n。数组D中的数据随着算法的逐步进行要不断地修改n定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使Dw的值最小。于是从源点到达w只通过S中的顶点，把 w 加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离：取Dv和Dw+costwv中值较小的作为新的Dvn重复上述，直到S中包含V中其余各顶点的最短路径。V0 V1 V2 V3 V4 V5 V0 10 30 100 V1 5 V2 50 V3 10 V4 20 60 V5 V0,V2,V4,V3,V5 ,V1V0,V2,V4,V3,V5 V0,V2,V4,V3V0,V2,V4V0,V2S=V0V1V5V3V4V2VjV5V4V3V26030501060V0,4,3,530501090V0,4,53050V0,4,310100V0,530V0,460V0,2,310100V0,5 30V0,410V0,2V1i=5i=4i=3i=2i=1D终点V0V2V1V4V5V355030101010060207.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= arcsijD(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的最短路径的长度。0 4 11 6 0 2 3 0各顶点间的最短路径及其路径长度 最短路径弗洛伊德举例 0 4 11 6 0 2 3 021CABCABCBCAABCA