数据结构第八章图ppt课件.ppt

1,数 据 结 构（第八章 图） Data Structures胡学钢 张 晶计算机与信息学院 2009年2月,2,第八章 图 (Graph),第八章 图（Graph) 8.1 基本概念和运算 8.2 图的存储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径,3,8.1 基本概念和运算,图 由顶点集V和连接顶点的弧集E所组成的结构， 记作 G = ( V, E )。 其中弧的形式为， 表示从顶点Vi到Vj之间有一条弧，图形表示为： Vi Vj 有向图例：如右图中的G1就是一个有向图： 其中： 顶点集合 V=1，2，3，4 弧集 E= , , , , ,4,8.1 基本概念和运算,如果顶点间的关系是相互的，即弧的两端没有方向，则图为无向图。其中的弧称为边。边的形式为(Vi,Vj)，图形表示为： Vi Vj例：如右图中的G2就是一个无向图： 其中： 顶点集合 V=1，2，3，4 边集 E= （1,2）,（1,3）,（1,4） （2,4）,（3,4） ,5,8.1 基本概念和运算,若G中每条边（弧）对应一个数值表示关系的程度，则称图G为网络。 例： 图G3 就是一个网络 对图G = ( V, E )，若存在G1=(V1，E1)， 满足V1V，E1E。则G1是G的子图。 例如：右图G4 就是G2 的子图。,6,8.1 基本概念和运算,顶点间关系： 如果 E 则称 Vi，Vj相邻接， Vi邻接到Vj，Vj邻接自Vi。 例如，右 图中， V1邻接到V2，V4邻接自V3 若( Vi,Vj )E则称Vi，Vj相邻接 顶点的度 顶点的邻接点的数目。 有向图中：入度，出度。 度入度出度。,7,8.1 基本概念和运算,路径 若 顶点序列Vi1，Vi2，Vik， 满足E或 者(Vil，Vi(l+1)E）（l=1,2,k-1）， 则该顶点序列Vi1，Vi2，Vik 构成一条路径。 例: 图G1中，1,2,4,1,3,4是一条路径简单路径 中间经过的顶点不重复的路径。 例:图G1中，( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径。回路 首尾相同的路径。 例如， ( 1,3,4,1 )简单回路 简单路径 + 回路,8,8.1 基本概念和运算,若无向图中任意两点间都存在路径 则称为连通图。 否则，称为不连通图（非连通图）。 非连通图包含若干连通分量 极大连通子图。 若有向图中的任意两点间可以互相到达 则称为强连通图。,9,8.1 基本概念和运算,若无向图中任意两点间都有一条边 则称为无向完全图。 （共有n (n-1) / 2条边）若有向图中每个顶点到其余各点均有一条弧 则称为有向完全图。 （共有n (n-1) 条边）,10,8.1 基本概念和运算,若无向图满足：连通并且无回路 则称为树。 树的定义有如下几个等价的描述： 有最少边数的连通图。 有n-1条边的连通图。 连通的无环图。有向树 如果在有向图中， 有一个顶点的入度为0，其余顶点的入度为1， 则称此图为有向树。 并称其中入度为0的顶点为有向根。 右下图就是一个有向树，其中顶点1就是有向根。,11,8.1 基本概念和运算,图的运算： 基本运算： 初始化图 插入顶点 插入边（弧） 修改权值 删除顶点 删除边（弧） 求指定顶点的邻接点 常用运算： 遍历,12,8.1 基本概念和运算,邻接点的求解方法： 具体实现依赖于图的存储结构， 可以考虑用两个运算来实现求解： int firstadj(G,v); 返回顶点v的第一个邻接点号。 若不存在时，返回0（或定义为-1）。 int nextadj(G,v,w); 返回顶点v的邻接点中处于邻接点w之后的邻接点号。 若不存在时，返回0（或定义为-1）。,13,8.2 图的存储,图的存储 图结构在计算机中的存储形式1. 邻接矩阵 （1）不带权值 假设图中有n个顶点。则采用nn的矩阵A来表示， 1 E 其中 Aij 0 否则例：,0 1 1 00 0 0 10 0 0 11 0 0 0,行的方向：发出的弧列的方向 ：进入的弧,14,8.2 图的存储,（2） 网络的表示方法 wij E Aij 0 或 否则例：, 4 3 54 23 65 2 6 ,0 1 1 11 0 0 11 0 0 11 1 1 0,无向图的邻接矩阵对称,15,8.2 图的存储,2. 邻接表表示法 将邻接点构成链表 例：,data,firstadj,16,8.2 图的存储,逆邻接链表 将“邻接自”的顶点连成链表,data firstadj,data firstadj,代表弧,17,8.3 图的遍历,图的遍历访问图中所有顶点一次且仅且一次。 深度优先搜索遍历 图的两种遍历算法 广度优先搜索遍历8.3.1 深度优先搜索遍历（Depth First Search) 这一问题求解包括几个部分。 1. 基本算法 从顶点v0出发深度优先搜索遍历图G的dfs (v0)描述如下： (1) 访问v0； (2) 依次从v0的未被访问过的邻接点出发深度遍历。,18,dfs(8),dfs(9),dfs(4),dfs(3),8.3.1 深度优先搜索遍历,下面以下图为例来讨论dfs算法的执行过程：调用dfs(1),此箭头表示是从遍历运算dfs(1)中调用dfs(2)，即从顶点1直接转到2,此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中，即从顶点3返回到2,9,dfs(1),dfs(2),dfs(5),dfs(6),dfs(7),dfs(10),在访问顶点3后，由于顶点3的邻接点已全被访问，故dfs（3）执行到此结束，应返回到调用层，即返回到dfs(2),dfs(1)包含如下两部分操作：（1）访问顶点1；（2）依次执行dfs(2)和dfs(8),19,8.3.1 深度优先搜索遍历,将dfs（1）执行过程中所搜索的边连接起来（有标注的边），得到一棵生成树-dfs生成树。,原图及其搜索示意图,dfs(1)生成树,20,8.3.1 深度优先搜索遍历,下面讨论dfs算法的设计。为此，先回顾一下dfs (v0)的描述： (1) 访问v0； (2) 依次从v0的未被访问过的邻接点出发深度遍历。 分析：由算法描述可知： 访问顶点v0的基本操作： 可用visite(v0)简单表示。 设置访问标志数组visited ，并约定： 某顶点vi未被访问时， visitedi=FALSE（初值） vi被访问过后， visitedi=TRUE（初值） 求邻接点可以采用两个函数： firstadj(G,v) ：返回v的第一个邻接点（号），或0（不存在时）。 nextadj(G,v,w);返回v的第邻接点中处于邻接点w之后的邻接点号, 或0（不存在时）,访问v0时， visitedi=TRUE;,21,Y,N,8.3.1 深度优先搜索遍历,由讨论可得到dfs算法的流程图如下：由此得深度遍历基本算法dfs(v0)如下 : void dfs(int v0) visite(v0); visitedv0=TRUE; w=firstadj(G,v0); while(w!=0) if(!visitedw) dfs(w); w=nextadj(G,v0,w); ,N,visite(v0); visitedv0=TRUE;,W=0?,W被访问过？,dfs(w);,w=nextadj(G,v,w);,w=firstadj(G,v) ：,22,8.3.1 深度优先搜索遍历,问题： （1）dfs算法是否适用于有向图？ （2）如何设置标志数组visited的初值？ 能否在dfs算法中设置？ （3）从某顶点出发是否能保证访问到所有顶点？ 或者说：选择一个起点调用一次dfs算法，能否实现对整个图的遍历？2. 遍历整个图的算法 dfs算法在应用于非连通图，或者是某些有向图时， 某一次调用就不能保证访问到所有顶点。如下图所示。,23,8.3.1 深度优先搜索遍历,为此，需要重新选择起点来调用dfs算法。 如何选择新的起点？ 起点应满足什么条件？将对访问标志数组的赋初值运算， 以及选择起点的控制合在一起，构成对整个图的遍历算法如下：void travel_dfs(graph G) for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if(!visitedi) dfs(i); ,24,8.3.1 深度优先搜索遍历,3. 深度遍历算法的应用问题： （1）如何设计算法以判断给定的无向图是否是连通的？ （2）如何设计算法以求解给定的无向图中的边数？ （3）设计算法以判断给定的无向图是树。 （4）设计算法以判断给定的有向图是以v0为根的有向树。 （5）设计算法以判断图中的一个节点是否为关节点。,25,8.3.1 深度优先搜索遍历,例1 设计算法以求解无向图G的连通分量的个数。分析：对无向图G来说，选择某一顶点v执行dfs(v)， 可访问到所在连通分量中的所有顶点 因此，选择起点的次数就是图G的连通分量数， 这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。 另外，考虑到要求求解连通分量数， 因而可以将算法设计为整型函数。 具体算法如下：,26,8.3.1 深度优先搜索遍历,int numofGC(graph G) int i; int k=0; / k用于连通分量的计数 for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE) k+; dfs(G,i); /用k来累计连通分量个数 return k ;,遍历整个图的算法dfs_travel中的原来的部分,27,8.3.1 深度优先搜索遍历,例2 设计算法求出无向图G的边数。算法如下：void dfs (graph G, int v ) int w; visitedv=TRUE; /设置访问标志（访问结点的其它操作被省去） w=firstadj(G,v); while (w!=0) E+; /此处意味着找到一条边，故累计到变量E中 if (visitedw=FALSE) dfs(G,w); w=nextadj(G,v,w); ,dfs算法中原有的操作,28,8.3.1 深度优先搜索遍历,int Enum (graph G ) int i; E=0; /全局变量E记录整个图中的边数 for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE;) dfs(G,i); return E/2;,遍历整个图的算法dfs_travel中的原来的部分,29,8.3.1 深度优先搜索遍历,4. 深度遍历算法的应用二例3：设计算法，将1-n(=20,或其他数)放在一个环上，使环上任意两个相邻元素的和为质数。分析：可以用图来描述该问题： 用顶点表示一个数 若两个数的和为质数， 则对应顶点之间有一条边。 例如，若n=10，对应图如右所示。在这一表示下，问题转化为：求图中包含所有顶点的简单回路。如图所示的一个解。（1，2，3，4，7，6，5，8，9，10）,30,8.3.1 深度优先搜索遍历,算法设计中需要注意的： 通过在dfs算法的基础上变化而得： （1）路径的记录：需要增加变量或参数以记录路径，因此，不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。 （2）若某些走法行不通，需要重来，为此，要恢复visitedi标志。 （3）需要判断首尾相接。,31,8.3.1 深度优先搜索遍历,算法构思如下:(1)设环上已有k个元素（0kn）。(2)若kn, 且不在当前路径上的顶点中存在与Bk相邻的， 则依次从余下的顶点中取出与Bk相邻的顶点放置在Bk+1中, 转(1)。(3)若kn，而在余下的这些顶点中找不到一个与BK相邻的顶点， 或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，因而须从环上去掉BK，转(1)。(4)若k=,有两种情况: (a)Bn与B1相邻接, 说明已求得一解, 则输出求解结果, 然后返回。 (b)Bn与B1不邻接，说明前面的放置法不行, 即不构成环, 因而需要重新放置，即要去掉Bn和Bn-1，然而转(1)。为避免遗漏某种放置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。,32,8.3.1 深度优先搜索遍历,采用递归方式实现如下： 其中visited为标志数组，表示各结点是否在当前的路径上。void getcc(int k) / A,B,visited为全局变量，k初值为1，B1固定为1 int i; if (k=n / 取消顶点i的放置，以便可被重新放入 调用前，要产生邻接矩阵 A的值。数组visited全置为FALSE, visited1置为TRUE。k为1,B1为1。本递归算法利用函数调用及返回实现搜索与回溯，若不用递归，本算法则较为麻烦。试模拟执行之。,33,8.3.2 广度优先搜索遍历,8.3.2 广度优先搜索遍历（Breadth_first search) 广度优先遍历 由近及远逐层访问顶点（典型的层次遍历） 1. 基本算法 从顶点v0出发广度优先搜索遍历图的算法bfs(v0): （1）访问v0 （2）依次访问v0的各邻接点。 （3）设最近一层访问序列为vi1，vi2，vik， 则依次访问 vi1，vi2，vik的 未被访问过的邻接点。,34,8.3.2 广度优先搜索遍历,bfs(1)的执行过程如下图所示。其中用红线标注搜索路线。将搜索的便连起来得到bfs生成树。,bfs生成树,35,8.3.2 广度优先搜索遍历,算法构思： (1) 设访问标志数组； (2)为了能依次访问上一层次的访问序列中的各顶点的邻接点， 需要设置一个结构以保存上一层次的顶点， 这一结构还要满足这样的要求： 这一层中最先被访问的顶点，其后继也应被最先检测到。 由此可知，这一结构应是队列。 (3)既然涉及到队列（不妨Q），则需要安排队列的运算： (a) 初始化； (b) 入队：每访问一个顶点v，除了访问操作、设置标志外，还要将其入队。 (c) 出队：从队列中删除一个顶点v，这意味着要依次访问v的所有未被访问过的邻接点。,36,8.3.2 广度优先搜索遍历,广度遍历的基本算法如下：void bfs(int v0) Queue Q; visite(v0); visitedv0=TRUE; Q.append(v0); while(!Q.Empty() v=Q.Serve(); w=firstadj(G,v); while(w!=0) if(!visitew) visite(w); visitedw=TRUE; Q.append(w); w=nextadj(G,v,w); ,37,8.3.2 广度优先搜索遍历,2. 遍历整个图的算法 void travel_bfs(graph G) for(i=1;i=n;i+) visitedi=FALSE; for(i=1;i=n;i+) if(!visitedi) bfs(i); 3.广度遍历算法的应用例：迷宫中的最短路径算法,38,8.4 最小生成树,问题：修建一个连接各个小区与煤气供应站点之间的管道，使得造价成本最低，即构造一颗最小生成树。但是如何求解？对应模型：树结构，生成树，最小生成树8.4.1 prim算法 1. 基本思想 在满足如下条件的边中选出一条最小的边： 一端已选，另一端未选。 因此，该算法需要给出起点，以作为已选顶点。 2. 实例 对右图所示图， 用Prim算法求最小生成树。,39,8.4 最小生成树,40,8.4 最小生成树-求解过程的表格化求解,1,1,6,1,6,5,1,6,5,4,1,6,5,4,3,1,6,5,4,3,2,(1,2)/12,(1,3)/,(1,4)/,(1,5)/9,(1,6)/9,(1,2)/12(6,2)/15,(6,3)/17,(6,4)/20,(1,5)/9(6,5)/9,(6,4)/20(5,4)/4,(1,2)/12 (6,2)/15,(6,3)/17,(1,2)/12 (6,2)/15,(6,3)/17(4,3)/3,(1,2)/12 (6,2)/15(3,2)/6,41,8.4 最小生成树,3.算法Prim算法的简要描述（设起点为v0）： 设置各候选边(v0,vi)； for (i=1; i=n-1; i+) 从候选边中找出权值最小的边(v,vk)； /其中v已选边，vk未选 将vk设置为已选顶点； 调整候选边集合-调整新入选顶点和未选顶点之间的边的集合 由此可知，需要考虑如下几个方面的实现：（1）已选顶点的标识：可用数组来或集合来存储（或形式化描述）。（2）候选边的存储 ： 虽然每个顶点可能对应多个候选边，但只要最小的一个， 因此，用一个数组也可以，不妨用edges（下标用1-n即可）,42,8.4 最小生成树,初始化候选边数组edges； U=v0；for (i=1; i=n-1; i+) k=最小候选边的未选的一端； U=U+k； 以k修改edges； 注：edges的元素可以设置为v 思考：权值最小的边一定在最小生成树中么？ 分析 : prim算法的时间复杂度？,43,8.4 最小生成树,void prim(graph G,graph ,初始化候选边数组edges,初始化已选边数组selected,rim算法的时间复杂度是O(n2)。,设置起始点已选,从候选边中找出权值最小的边,将k设置为已选顶点,调整候选边集合,44,8.4 最小生成树,2. 实例判断构成回路的经典方法：电位法： 初始状态：各顶点的电位=顶点号 每当选择一条边时，相连通的顶点的电位全都按照其中最小的值设置。 由此可知新的候选边是否和已选边构成回路 -判断方法？,Kruskal算法 1.基本思想 反复在满足如下条件的边中选出一条最小的边 和已选边不构成回路。,1,3,2,4,5,6,7,1,2,1,1,1,1,1,45,8.4 最小生成树,3算法实现的讨论 Kruskal算法的简要描述： T=(V,) ; /初始化生成树T while(T中所含边数n-1) 从E中选取当前最短边(u,v)； 从E中删去边(u,v)； if ( (u,v)与T中边不构成回路) 将边(u,v)加入T中； ,需解决问题：（1）候选边的存储 （2）判断所选择的边和已选的边不构成回路？,分析Kruskal算法的时间复杂度为(eloge)、(n3) 。其时间性能和空间性能都不是很如意。,46,8.4 最小生成树Kruskal算法练习,Kruskal算法 基本思想 反复在满足如下条件的边中选出一条最小的边 使其和已选边不构成回路。,Kruskal最小生成树,47,8.5 有向无环图的应用,工程由多项活动构成，且活动之间存在一定制约。 工程问题： 1) 工程能否顺利进行？ 2) 工程至少需要的时间？ 3) 工程中哪些是关键环节？8.5.1 拓扑排序对第一类问题的求解：用图来表示工程：其中， 用顶点表示活动；弧表示活动之间的制约关系。 称这种图为AOV网(Activity On Vertex Network)。,工程是否顺利进行？,AOV网是否存在有向回路,48,8.5.1 拓扑排序,如何判断AOV网中是否存在有向回路？解决方法：(1)用深度遍历要做许多试探性工作；(2)用产生(包含所有) 顶点序列的方法，顶点序列满足： 在图中，若顶点vi到顶点vj存在路径， 则在序列中，顶点vi领先于顶点vj。 满足上述条件的顶点序列称为拓扑序列， 产生这一序列的过程称为拓扑排序。由拓扑排序如何判断是否存在有向回路？ 结论：如果能产生拓扑序列， 则说明AOV网中无回路，否则有回路。,49,8.5.1 拓扑排序,拓扑排序算法简单描述： 找一个入度为0的顶点v输出； 删除v及相关弧； 重复，直到无入度为0的顶点为止。 此时，若所有顶点被输出，则无回路， 否则有回路。,50,8.5.1 拓扑排序实例,1,6,6,6,6,对下图所示AOV网进行拓扑排序,51,8.5.1 拓扑排序,判断有无回路的条件：是否有拓扑序列。思考： 入度数组Ind （数组初始化的实现）； “删除v”的实现后继的入度减一； 找入度为0的顶点 将入度为0的待输出顶点放到栈中，若出现入度为0 的顶点则入栈。拓扑排序算法设计 拓扑排序算法： 初始化入度数组Ind （若出现0入度顶点，则入栈s）； 若栈s为空，则跳出循环，转到 v=pop(s)并输出v； 对v的所有后继w实现：Indw-1；若Indw=0；则w入栈； 转； 判断是否存在回路。,拓扑排序算法简单描述：找一个入度为0的顶点v输出；删除v及相关弧；重复，直到无入度为0的顶点为止。此时，若所有顶点被输出，则无回路， 否则有回路。,52,8.5.1 拓扑排序,栈的演示,1,2,3,5,4,6,0,0,1,1,1,0,0,0,53,8.5 有向无环图的应用拓扑排序,Bool toposort(graph G) get_Ind(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i); while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE; ,分析 若图采用邻接矩阵来存储，则算法复杂度为(n2)；若图采用邻接表来存储，则算法复杂度为(n+e)。,54,8.5 有向无环图的应用练习,例:写出一个拓扑序列所以，其中一种拓扑序列为： 2 5 1 4 7 3 6 8 9 10思考：写出所有的拓扑排序。,55,8.5.2 关键路径,另一类工程问题： 工程至少需要的时间？ 工程中哪些是关键环节？为此，用图来表示工程：其中，用弧表示活动；用弧的权值表示活动的持续时间；用弧两端的顶点分别表示活动的开始和结束，即瞬间行为或事件。 这种图称为AOE网(Activity On Edge Network)。,56,8.5.2 关键路径,在AOE网中， 称开始点为源点， 称结束点为汇点。 整个工程所需要的最少时间：是从源点到汇点之间的最长的一条路径-关键路径(critical path)。由此可知，问题变成求解 求解AOE网中的关键路径,57,8.5.2 关键路径,如何求解关键路径？可分2个步骤来求解： （1）求解各顶点事件的最早发生时间 由此可得到汇点事件的最早发生时间 -整个工程最少需要的时间（2）反推各顶点时间的最迟发生时间由此可得到不能耽误的活动，此类活动连起来，构成关键路径。,58,8.5.2 关键路径,各顶点事件最早发生时间的求解：为求最长路经，则需求各顶点对应事件的最早发生时间E ;每个顶点事件的最早发生时间，依赖于其前驱顶点事件的最早发生时间。源点对应事件的最早发生时间为0,3,4,5,9,8,14,13,12,19,0,59,8.5.2 关键路径,程序实现讨论：可在拓扑排序算法的基础上添加操作来实现：每当找到一个后继顶点w，计算Ew，计算公式如下： Ew=maxEw, Ev+dutv,w对应语句： if (Ev+durv,wEw) Ew=Ev+dutv,w; 还要注意的问题： 各顶点Ei值得初始化,Bool toposort(graph G) get_Ind(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i); while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE; ,60,8.5.2 关键路径,各顶点事件最迟发生时间的求解为不耽误工期，则需要求出各顶点对应事件的最迟发生时间L .每个顶点事件的最迟发生时间取决于其后继顶点事件的最迟发生时间。,61,8.5.2 关键路径,最迟发生时间的求解,1,2,3,4,5,6,7,8,9,10,a1=3,a3=5,a2=4,a5=3,a4=6,a8=5,a9=4,a6=4,a10=3,a12=6,a11=4,a15=4,a14=6,a13=5,a7=3,3,4,5,9,8,14,13,12,19,19,15,13,14,9,10,7,6,3,0,0,62,8.5.2 关键路径,程序实现讨论：可在拓扑排序算法的基础上添加操作来实现：每当找到一个前驱顶点w，计算Lw, 计算公式如下： Lw=minLw, Lv-dutw,v 对应语句： if (Lv-dutw,vLw) Lw= Lv-dutw,v; 还要注意的问题： 各顶点Li值得初始化。 算法与拓扑排序的关系。,Bool toposort(graph G) get_Ind(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i); while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE; ,63,8.5.2 关键路径,如何求解AOE网中的关键路径？ 关键路径上的事件最早发生时间和最晚发生时间相等； 关键路径上的活动的开始和结束事件发生的时间差等于活动的持续时间。,64,8.5.2 关键路径,关键路径的求解方法及路径,1,2,3,4,5,6,7,8,9,10,a1=3,a3=5,a2=4,a5=3,a4=6,a8=5,a9=4,a6=4,a10=3,a12=6,a11=4,a15=4,a14=6,a13=5,a7=3,3,4,5,9,8,14,13,12,19,19,15,13,14,9,10,7,6,3,0,0,关键路径：（1,2,5,7,10）和（1,2,5,8,10） 关键活动：a1，a4，a8，a9，a13，a14,65,8.6 最短路径(Shortest path),从单个点到其余各点之间的最短路径 Dijkstra算法各点之间的最短路径 Floyd算法,66,8.6 最短路径Dijkstra算法,从单个点到其余各点间的最短路径Dijkstra算法 基本思想 按照最短路径长度不减的次序求各顶点的解。 若已知道路v0v1v2v3vn-1vn是v0到vn最近的路， 则途经的某顶点vi也为v0到vi最短的路。,67,8.6 最短路径Dijkstra算法描述,方法如下： （其中：pathv和distv表示从v0到v的最短路径及其长度）（1）对v0以外的各顶点vi，若存在，则将其作为v0到vi的（暂时的）最短路径存放到pathv中，将其权值作为对应的路径长度存放到distv中。（2）从未解顶点中选择一个dist值最小的顶点v，则当前的pathv和distv就是顶点v的最终解。（3）由于某些顶点经过v可能会使得从v0到该顶点的路径更近一些，因此，应修改这些顶点的路径及其长度的值。（4）重复（2）（3），直到所有顶点求解完毕。,68,8.6 最短路径Dijkstra算法实例,1,0,12,3,(1)初始化:1到v,若有边,则pathv=边;disti=边的值,(2)选出disti为最小值,则pathi为1到i的最短路径,(3)修改经过i更近的路径,(4)重复（2）（3）,69,8.6 最短路径Dijkstra算法实例,实例：,0,12,3,(),(1,2),(1,3),(),(),(),(1,3,2),8,5,(1,3,4),(1,3,5),10,(1,3,4,6),14,(1,3,5,6),12,70,8.6 最短路径Dijkstra算法实现,练习：,void Dijkstra( graph G,for(i=1;i=n;i+) mind= ; for(j=1;j=n;j+) if( !solvedj ,图采用邻接矩阵或邻接表来存储，算法复杂度均为(n2)。,71,8.6 最短路径Dijkstra算法练习,练习：,72,8.6 最短路径Floyd算法,各点间的最短路径 Floyd算法 基本思想 通过矩阵序列实现A(0),A(1),A(n)， 其中A(k)中的元素A(k) i,j代表： 顶点i到顶点j的当中间经过的顶点号不大于k时的最短路径长度。 如何求解各矩阵？ Floyd算法采用的是由A(k-1) 矩阵求A(k)的方法来实现的。,i,j,各顶点号k,73,8.6 最短路径Floyd算法,由A(k-1) 矩阵求A(k)的方法 可通过求得矩阵中的各元素A(k)ij来实现求解 A(k)ij的求解：可由A(k-1) 矩阵中的相关元素来求得： 分两种情况讨论：经过顶点k时，路径更短， 即A (k-1) ik + A (k-1) kj A (k-1) ij 则A (k) ij =A (k-1)ij,i,j,k,路径中各顶点k-1，对应A (k-1) ik,路径中各顶点k-1，对应A (k-1) kj,路径中各顶点k-1，对应A (k-1) ij,74,8.6 最短路径Floyd算法实例,3,6,20,6,5,2,3,4,4,20,6,5,A0=,1 2 3 4,1 2 3 4,2,3,4,7,4,20,22,6,5,2,6,4,4,25,27,2,3,4,7,20,22,求各顶点间的最短路径,2,3,1,4,3,75,8.6 最短路径Floyd算法实现,Floyd算法的核心算法： for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) If (A (k-1) ik + A (k-1) kjA (k) ij ) A (k) ij = A (k-1) ik + A (k-1) kj; pathij = pathik+pathkj; else A (k) ij = A (k-1) ij;考虑用同一个矩阵A节省矩阵序列的存储，则上述算法转化为： for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j=n;j+) if ( Aik+Akj Aij ) Aij=Aik+Akj; pathij=pathik+pathkj;,分析算法复杂度均为(n3),