第12章 图(二)

1、计算机与控制工程学院第第1212章章 图（二）图（二）计算机与控制工程学院主要内容主要内容 最短路径最短路径 拓扑排序拓扑排序 关键路径关键路径2计算机与控制工程学院最短路径问题最短路径问题 无权图的最短路径问题无权图的最短路径问题 比较简单，即两点之间边数最少的路径比较简单，即两点之间边数最少的路径 有向带权图有向带权图的最短路径问题的最短路径问题 可理解为两地间交通费用最少问题可理解为两地间交通费用最少问题 分为单源最短路径、每对点最短路径两类分为单源最短路径、每对点最短路径两类3计算机与控制工程学院单源最短路径单源最短路径 有向图有向图G G，每条边都有非负权重（耗费），每条边都有非负权

2、重（耗费） 路径长度路径长度路径中边的权重之和路径中边的权重之和 单源最短路径：给定源顶点单源最短路径：给定源顶点s s，求它到其他，求它到其他任意顶点（目的顶点）的最短路径任意顶点（目的顶点）的最短路径4计算机与控制工程学院单源最短路径例单源最短路径例5计算机与控制工程学院DijkstraDijkstra算法算法 S S：“已求出最短路径顶点集合已求出最短路径顶点集合”，初始为，初始为ss L=V - SL=V - S 每个步骤从每个步骤从L L选取一个顶点选取一个顶点v v加入加入S S 贪心准则：贪心准则：v v是是L L中距中距s s距离最短者距离最短者 新最短路径新最短路径= =已有

3、最短路径已有最短路径+ +一条边一条边每个顶点无需保存其完整路径，保存路径中它每个顶点无需保存其完整路径，保存路径中它的前一顶点即可的前一顶点即可6计算机与控制工程学院实现实现 数组数组p p：保存路径（上例：保存路径（上例：0, 1, 1, 3, 40, 1, 1, 3, 4） pipi：最短路径中顶点：最短路径中顶点i i的前驱顶点的前驱顶点 从终点开始，逆向即可获取路径从终点开始，逆向即可获取路径 数组数组d d：当前最短路径长度：当前最短路径长度 i i在在S S中，中，didi：s si i的真正最短路径长度（最终结的真正最短路径长度（最终结果）果） i i在在L L中，中，didi

4、：当前最短路径长度：当前最短路径长度s sj(j(S)S)i i的路径长度（最短者）：的路径长度（最短者）：dj+aji dj+aji 从从L L中选择中选择v v加入加入S S后，后，S S发生变化，发生变化，L L中的中的didi可能变可能变得更小，应进行更新得更小，应进行更新7计算机与控制工程学院运算实例：解题形式运算实例：解题形式1 1 1 2 3 4 5d=0, 4, 2, , 8p=0, 1, 1, 0, 1 1 2 3 4 5d=0, 4, 2, 3, 8 p=0, 1, 1, 3, 1 1 2 3 4 5d=0, 4, 2, 3, 6 p=0, 1, 1, 3, 4 1 2 3

5、 4 5d=0, 4, 2, 3, 6 p=0, 1, 1, 3, 4 1 2 3 4 5d=0, 4, 2, 3, 6 p=0, 1, 1, 3, 48S=1S=1, 3, 13S=1, 3, 4, 134S=1, 3, 4, 2, 12S=1, 3, 4, 2, 51345计算机与控制工程学院运算实例运算实例9计算机与控制工程学院10计算机与控制工程学院11计算机与控制工程学院12计算机与控制工程学院DijkstraDijkstra算法伪代码算法伪代码1)1) 初始化初始化d d i i=a a s si i （11i in n）对于邻接于对于邻接于s s的所有顶点的所有顶点i i，置，置

6、p p i i=s s，对于其余，对于其余的顶点置的顶点置p p i i=0=0对于对于p p i i 0 0的所有顶点建立的所有顶点建立L L表表2)2) 若若L L为空，终止，否则转至为空，终止，否则转至3)3)3)3) 从从L L中删除中删除d d值最小的顶点值最小的顶点4)4) 对于与对于与i i邻接的所有还未到达的顶点邻接的所有还未到达的顶点j j，更新，更新d d j j 值为值为minmin d d j j, , d d i i+a a i ij j若若d d j j 发生了变化且发生了变化且j j还未在还未在L L中，则置中，则置p p j j=i=i，并将并将j j加入加入L

7、 L，转至，转至2 213计算机与控制工程学院无序链表实现无序链表实现templatevoid AdjacencyWDigraph:ShortestPaths(int s, T d, int p)/ Shortest paths from vertex s, return shortest / distances in d and predecessor info in p. if (s n) throw OutOfBounds(); Chain L; / list of reachable vertices for / which paths have yet to be found Cha

8、inIterator I; 14计算机与控制工程学院无序链表实现（续）无序链表实现（续） / initialize d, p, and L for (int i = 1; i = n; i+) di = asi; if (di = NoEdge) pi = 0; else pi = s; L.Insert(0,i); 15计算机与控制工程学院无序链表实现（续）无序链表实现（续） / update d and p while (!L.IsEmpty() / more paths exist / find vertex *v in L with least d int *v = I.Initial

9、ize(L); int *w = I.Next(); while (w) if (d*w d*v) v = w; w = I.Next();16计算机与控制工程学院无序链表实现（续）无序链表实现（续）int i = *v; L.Delete(*v); for (int j = 1; j di + aij) dj = di + aij; if (!pj) L.Insert(0,j); pj = i; 17计算机与控制工程学院每一对点的最短路径每一对点的最短路径 所有点对间的最短路径，所有点对间的最短路径，all-pairs shortest-all-pairs shortest-paths pr

10、oblempaths problem，n(n-1)n(n-1)条条 简单算法：每个顶点执行单源最短路径算法简单算法：每个顶点执行单源最短路径算法18计算机与控制工程学院FloydFloyd算法算法 顶点编号为顶点编号为1 1n n c(i,j,k)c(i,j,k)：i ij j的的“最短路径最短路径”长度长度加了加了限制条件，路径中顶点的最大编号为限制条件，路径中顶点的最大编号为k k 存在边存在边c(i, j, 0)=c(i, j, 0)=的长度的长度 不存在边不存在边c(i, j, 0)=+c(i, j, 0)=+ c(i, i, 0)=0c(i, i, 0)=0 c(i, j, n)c(

11、i, j, n)最短路径长度最短路径长度19计算机与控制工程学院FloydFloyd算法算法 例例15.615.6：考虑上图：考虑上图 k=0, 1, 2, 3k=0, 1, 2, 3，c(1, 3, k)= +c(1, 3, k)= + ；c(1, 3, 4)=28c(1, 3, 4)=28 k=5, 6, 7k=5, 6, 7，c(1, 3, k)=10c(1, 3, k)=10； k=8, 9, 10k=8, 9, 10，c(1, 3, k)=9c(1, 3, k)=9最短路径最短路径20计算机与控制工程学院如何计算如何计算c(i, j, k)c(i, j, k) 顶点最大编号不超过顶点

12、最大编号不超过k k，两种情况，两种情况 路径不包含路径不包含k k，c(i, j, k)=c(i, j, k-1)c(i, j, k)=c(i, j, k-1) 包含包含k k，c(i, j, k)=c(i, k, k-1) + c(k, j, c(i, j, k)=c(i, k, k-1) + c(k, j, k-1)k-1) c(i,j,k)=minc(i,j,k-1), c(i,j,k)=minc(i,j,k-1), c(i,k,k-c(i,k,k-1)+c(k,j,k-1)1)+c(k,j,k-1) 递归算法，递归算法，Q Q(n2(n2n n) ) 迭代计算迭代计算Q Q(n(n3

13、 3) )21计算机与控制工程学院迭代计算伪代码迭代计算伪代码/ / /寻找最短路径的长度寻找最短路径的长度/ / /初始化初始化c c（i i，j j，1 1）for (int i=1for (int i=1； i = n ; i +)i = n ; i +)for (int for (int j j=1; =1; j j=n; =n; j j+)+) c( i , c( i ,j j, 0) = a (i , 0) = a (i ,j j); / a ); / a 是长度邻接矩阵是长度邻接矩阵/ / /计算计算c ( i ,c ( i ,j j, k ) ( 0 k = n ), k )

14、( 0 k = n )for(int k=1;k=n;k+)for(int k=1;k=n;k+)for (int i=1;i=n;i+)for (int i=1;i=n;i+) for (int for (int j j= 1 ;= 1 ;j j = n ; = n ;j j+ + )+ + )if (c(i,k,k-1)+c(k, if (c(i,k,k-1)+c(k, j j, k - 1) c (i, , k - 1) c (i, j j, k - 1), k - 1) c(i, c(i, j j, k) = c(i, k, k - 1) + c(k, , k) = c(i, k, k

15、 - 1) + c(k, j j, k - 1) ;, k - 1) ;else c(i, else c(i, j j, k) = c (i, , k) = c (i, j j, k - 1);, k - 1);22计算机与控制工程学院FloydFloyd算法例算法例ABCDA013 B01C502D40C023计算机与控制工程学院FloydFloyd算法例（续）算法例（续）12341013 2013502440C0c(i,j,1)=min(c(i,j,0), c(i,1,0)+c(1,j,0)12341013 20135602440C124计算机与控制工程学院FloydFloyd算法例（续）

16、算法例（续）12341013 20135602440C1c(i,j,2)=min(c(i,j,1), c(i,2,1)+c(2,j,1)123410123 201356024450C225计算机与控制工程学院FloydFloyd算法例（续）算法例（续）123410123 201356024450C2c(i,j,3)=min(c(i,j,2), c(i,3,2)+c(3,j,2)123410123 2601335602410450C326计算机与控制工程学院FloydFloyd算法例（续）算法例（续）123410123 2601335602410450C3c(i,j,4)=min(c(i,j,3

17、), c(i,4,3)+c(4,j,3)123410123 2601335602410450C427计算机与控制工程学院最终代码最终代码templatevoid AdjacencyWDigraph:AllPairs(T *c, int *kay)/ All pairs shortest paths. / Compute cij and kayij for all i and j. / initialize cij = c(i,j,0) for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) cij = aij; kayij = 0; for

18、(i = 1; i = n; i+) cii = 0;28计算机与控制工程学院最终代码（续）最终代码（续）/ compute cij = c(i,j,k) for (int k = 1; k = n; k+) for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) T t1 = cik; T t2 = ckj; T t3 = cij; if (t1 != NoEdge & t2 != NoEdge & (t3 = NoEdge | t1 + t2 t3) cij = t1 + t2; kayij = k; 29计算机与控制工程

19、学院最终代码（续）最终代码（续）void outputPath(int *kay, int i, int j)/ Actual code to output i to j path. if (i = j) return; if (kayij = 0) cout j ; else outputPath(kay, i, kayij); outputPath(kay, kayij, j);30计算机与控制工程学院最终代码（续）最终代码（续）templatevoid OutputPath(T *c, int *kay, T NoEdge, int i, int j)/ Output shortest

20、path from i to j. if (cij = NoEdge) cout There is no path from i to j endl; return; cout The path is endl; cout i ; outputPath(kay,i,j); cout endl;31计算机与控制工程学院主要内容主要内容 最短路径最短路径 拓扑排序拓扑排序 关键路径关键路径32计算机与控制工程学院工程和有向无环图工程和有向无环图 有向无环图是描述复杂工程的有效工具有向无环图是描述复杂工程的有效工具 工程可以分解为多个活动（工程可以分解为多个活动（ActivityActivity）

21、活动之间具有前后约束关系活动之间具有前后约束关系 工程问题转化为工程问题转化为 工程能否顺利进行？工程能否顺利进行？ 完成工程的最短时间是多少？完成工程的最短时间是多少？33计算机与控制工程学院拓扑排序拓扑排序 偏序：集合中仅有部分成员之间可比较偏序：集合中仅有部分成员之间可比较 全序：集合中全体成员之间均可比较全序：集合中全体成员之间均可比较 拓扑排序拓扑排序（Topological SortTopological Sort）：由某个集合上）：由某个集合上的一个偏序得到该集合上的一个全序的一个偏序得到该集合上的一个全序V1V2V3V4V1V2V3V434计算机与控制工程学院AOVAOV图图

22、用顶点表示活动，用箭头表示活动间优先关系的用顶点表示活动，用箭头表示活动间优先关系的有向图称为顶点活动网络（有向图称为顶点活动网络（Activity On VertexActivity On Vertex，AOVAOV） 顶点顶点i i在顶点在顶点j j之前，意味着活动之前，意味着活动i i是活动是活动j j的先决条件的先决条件 显然不应该出现有向环，否则显然不应该出现有向环，否则“活动活动k k是它自己的先决是它自己的先决条件条件”，不成立，不成立35计算机与控制工程学院AOVAOV网络示例网络示例36计算机与控制工程学院拓扑序列例拓扑序列例 123456123456/p>

23、6、215346215346 142356142356不是！不是！37计算机与控制工程学院利用贪心算法进行拓扑排序利用贪心算法进行拓扑排序 在有向图中选一个没有前驱的顶点且输出在有向图中选一个没有前驱的顶点且输出 从图中删除该顶点和所有从其发出的箭头从图中删除该顶点和所有从其发出的箭头 重复上述两步，直至所有顶点均已输出，或者当重复上述两步，直至所有顶点均已输出，或者当前图中不存在无前驱的顶点为止前图中不存在无前驱的顶点为止38计算机与控制工程学院算法描述算法描述设设n n是有向图中的顶点数是有向图中的顶点数设设V V是一个空序列是一个空序列while while ( (truetrue)设设

24、w w不存在入边（不存在入边（v v, ,w w），其中顶点），其中顶点v v不在不在V V中中如果没有这样的如果没有这样的w w，breakbreak把把w w添加到添加到V V的尾部的尾部 ifif( (V V中的顶点数少于中的顶点数少于n n) )算法失败算法失败elseelseV V是一个拓扑序列是一个拓扑序列39计算机与控制工程学院算法示例算法示例40V1V2V3V4V6V5V1V2V3V4V5V2V3V4V5V2V3V5Step1 Step2 Step3 Step4计算机与控制工程学院算法细化算法细化数据结构的选择数据结构的选择 拓扑序列拓扑序列V V如何描述？如何描述？如何找出候

25、选顶点？如何找出候选顶点？ VV一维数组一维数组v v栈栈保存候选顶点保存候选顶点 InDegreeInDegree保存顶点当前入度保存顶点当前入度41计算机与控制工程学院算法实现算法实现 初始初始 V V为空为空 InDegreeInDegree保存图中顶点入度保存图中顶点入度 将入度为将入度为0 0的顶点压栈的顶点压栈 每个步骤每个步骤 弹出栈顶顶点弹出栈顶顶点p p，加入，加入V V 并将并将p p的每个邻接顶点的的每个邻接顶点的InDegreeInDegree值减值减1 1 若某个顶点的若某个顶点的InDegreeInDegree值变为值变为0 0，将其压栈，将其压栈42计算机与控制工

26、程学院实现实现bool Network:Topological(int v) int n = Vertices(); / Compute in-degrees int *InDegree = new int n+1; InitializePos(); / graph iterator array for (int i = 1; i = n; i+) / initialize InDegreei = 0;43计算机与控制工程学院实现（续）实现（续） for (i = 1; i = n; i+) / 遍历所有顶点的出边，计算入度遍历所有顶点的出边，计算入度 int u = Begin(i); wh

27、ile (u) InDegreeu+; u = NextVertex(i); / Stack vertices with zero in-degree LinkedStack S; for (i = 1; i = n; i+) if (!InDegreei) S.Add(i);44计算机与控制工程学院实现（续）实现（续） / Generate topological order i = 0; / cursor for array v while (!S.IsEmpty() / select from stack int w; / next vertex S.Delete(w); vi+ = w

28、; int u = Begin(w); while (u) / update in-degrees InDegreeu-; if (!InDegreeu) S.Add(u); u = NextVertex(w); DeactivatePos(); delete InDegree; return (i = n);时间复杂度是时间复杂度是O(n+e)45计算机与控制工程学院拓扑排序要点拓扑排序要点 入度为入度为0 0的顶点即没有前驱活动的，或前驱的顶点即没有前驱活动的，或前驱活动都已经完成的顶点，工程可以从这个顶活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续点所代表的活动开始或继续

29、 算法每输出一个顶点之后，要删去从这个顶算法每输出一个顶点之后，要删去从这个顶点发出的边，这意味着这个顶点所代表的活点发出的边，这意味着这个顶点所代表的活动已经完成，对于后续顶点所代表的活动来动已经完成，对于后续顶点所代表的活动来说，该前驱活动已经完成说，该前驱活动已经完成46计算机与控制工程学院拓扑排序要点拓扑排序要点 如果一个节点有多个直接后继，则拓扑排序如果一个节点有多个直接后继，则拓扑排序的结果通常不唯一的结果通常不唯一 由于由于AOVAOV网络中各顶点的地位是平等的，每网络中各顶点的地位是平等的，每个顶点的编号是人为的，因此可以按照拓扑个顶点的编号是人为的，因此可以按照拓扑排序的结果

30、重新安排顶点的序号，生成排序的结果重新安排顶点的序号，生成AOVAOV网络的新的邻接矩阵存储表示。其中，对角网络的新的邻接矩阵存储表示。其中，对角线以下可以全为零。线以下可以全为零。47计算机与控制工程学院小练习小练习 写出下图的所有拓扑排序结果写出下图的所有拓扑排序结果 提示：共有提示：共有7 7种种48V1V2V6V5V3V4计算机与控制工程学院主要内容主要内容 最短路径最短路径 拓扑排序拓扑排序 关键路径关键路径49计算机与控制工程学院AOEAOE网网 一个带权的有向无环图，其中顶点表示事件一个带权的有向无环图，其中顶点表示事件，边表示活动，权表示活动持续的时间，则，边表示活动，权表示活

31、动持续的时间，则该图称为该图称为AOEAOE（Activity On EdgeActivity On Edge）网）网左图所示工程：9个事件（里程碑）11项活动（必须完成的工作）V5含义是：a4和a5已完成a7和a8可开始50计算机与控制工程学院关键路径关键路径 将将AOEAOE网看作一个工程网看作一个工程 只有一个入度为只有一个入度为0 0的点（源点），一个出度为的点（源点），一个出度为0 0的的点（汇点）点（汇点） 完成整个工程需要多少时间？哪些活动是影响工完成整个工程需要多少时间？哪些活动是影响工程进度的关键？程进度的关键？ 关键路径关键路径（Critical PathCritical

32、Path） 从源点到汇点长度（时间和）最长的路径从源点到汇点长度（时间和）最长的路径 长度长度完成工程的最短时间完成工程的最短时间 上例：上例：(v(v1 1, v, v2 2, v, v5 5, v, v8 8, v, v9 9) )51计算机与控制工程学院关键活动关键活动 源点源点v v1 1v vi i的最长路径长度：的最长路径长度：事件事件v vi i的最早发生时间，的最早发生时间，v vi i发出的所有边（活动）的最早开始时间发出的所有边（活动）的最早开始时间 e(i)e(i)：活动：活动a ai i的最早开始时间的最早开始时间 最迟开始时间：最迟开始时间：l(i)l(i)，前提：不

33、影响工程进，前提：不影响工程进度度 l(i)=e(i)l(i)=e(i)：关键活动：关键活动 关键路径上的活动都是关键活动关键路径上的活动都是关键活动 通过计算通过计算l(i)l(i)、e(i)e(i)寻找关键活动寻找关键活动52计算机与控制工程学院l(i)l(i)和和e(i)e(i)的计算的计算 事件的最早发生时间事件的最早发生时间ve(j)ve(j)最迟发生时间最迟发生时间vl(j)vl(j) 活动活动a ai i由边由边表示表示dut()dut()表示其持续时间，则有表示其持续时间，则有 e(i)=ve(j) e(i)=ve(j) 含义是：活动含义是：活动i i要想开始至少需要等待的时间要想开始至少需要等待的时间 l(i)=vl(k)-dut()l(i)=vl(k)-dut() 含义是：活动含义是：活动i i开始之前最多空闲的时间开始之前最多空闲的时间jkaidut53计算机与控制工程学院ve(i)ve(i)的计算的计算 由由ve(0)=0ve(0)=0向前递推向前递推ve(j)=ve