图软件学院PPT课件

1、例 某工程源点：表示整个工程的开始（入度为零）。汇点：表示整个工程的结束（出度为零）。完成整个工程至少需要多少时间？为缩短工程的时间，应当加快哪些活动？325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第1页/共70页 从源点到各顶点的路径可能不止一条，路径长度也可能不同。只有各条路径上所有活动都完成了，整个工程才算完成。 因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。l路径长度：指路径上的各边权值之和。l关键活动：关键路径上的

2、活动。3 32 25 51 14 40 08 86 67 7a1=6a8=7a7=9a6=2a4=1a a5 5=1=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第2页/共70页 关键活动有关的量： 事件vj的最早发生时间ve(j): 从源点v0到vj的最长路径长度。 事件vj的最迟发生时间vl(j):保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟开始时间，等于ve(n-1)减去从vj到vn-1最长路径长度。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第3页/共70页 ve(0)=0v

3、e(1)= 6ve(2)= 4ve(3)= 5ve(4)= 7ve(5)= 7ve(6)= 16ve(7)= 14ve(8)= 18vl(8)= 18vl(7)= 14vl(6)= 16vl(5)= 10vl(4)= 7vl(3)= 8vl(2)= 6vl(1)= 6vl(0)= 0第4页/共70页 关键活动有关的量： 活动ai的最早开始时间e(i): 设活动ai在有向边上, e(i)是从源 点v0到vj的最长路径长度。因此e(i)=ve( j)。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第5页/共70页 关键

4、活动有关的量： 活动ai的最迟开始时间l(i): l(i) 是在不会引起时间延误的前提下，该活动允许的最迟开始时间。设活动ai在有向边上, 则 l(i)= vl(k)-weight()325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第6页/共70页 aie(i)l(i) 0 0 0 6 4 5 7 7 7 0 0 0 6 4 5 7 7 7 16 14 16 14 0 2 3 6 6 8 7 7 0 2 3 6 6 8 7 7 1010 16 14 16 14 a1 a2 a3 a4 a5 a6 a7 a8 a9 a

5、10 a11 第7页/共70页 关键活动： l(i) e(i) 表示活动ak 是没有时间余量的关键活动。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点为找出关键活动, 需要求各个活动的 e(i) 与 l(i)，以判别是否 l(i) e(i) 为求得e(i) 与 l(i)，需要先求得从源点V0到各个顶点Vj 的 ve(j) 和 vl(j)。第8页/共70页求关键活动算法求关键活动的基本步骤：对AOE网进行拓扑排序，按拓扑次序求出各顶点事件的最早发生时间ve，若网中有回路，则终止算法； 按拓扑序列的逆序求各顶点事件的最

6、迟发生时间vl;根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则i是关键活动。第9页/共70页 例 求关键活动 第1步ve(k)ve(0)0 k=0maxve(j)+ weight() E(G), k=1, 2, , n-1325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第10页/共70页 ve(0)=0ve(1)= ve(0)+weight()=0+6=6ve(2)= ve(0)+weight()=0+4=4ve(3)= ve(0)+weight()=0+5=5ve

7、(4)= maxve(1)+ weight()， ve(2)+ weight()=max6+1,4+1=7ve(5)= ve(3)+weight()=5+2=7ve(6)= ve(4)+weight()=7+9=16ve(7)= maxve(4)+ weight()， ve(5)+ weight()=max7+7,7+4=14ve(8)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,14+4=18第11页/共70页 例 求关键活动 第2步vl(j)ve(n-1) j=n-1minvl(k)- weight() E(G), j= n-2, n-3,03

8、25140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第12页/共70页 vl(8)= ve(8)=18vl(7)= vl(8)-weight()=18-4=14vl(6)= vl(8)-weight()=18-2=16vl(5)= vl(7)-weight()=14-4=10vl(4)= minvl(7)- weight()， vl(6)- weight() =min14-7,16-9=7vl(3)= vl(5)-weight()=10-2=8vl(2)= vl(4)-weight()=7-1=6vl(1)= vl(4)-

9、weight()=7-1=6vl(0)= minvl(1)- weight()， vl(2)- weight(), vl(3)- weight() = min6-6,6-4,8-5=0第13页/共70页 aie(i)l(i)li-ei 0 0 0 6 4 5 7 7 7 0 0 0 6 4 5 7 7 7 16 14 16 14 0 2 3 6 6 8 7 7 0 2 3 6 6 8 7 7 1010 16 14 16 14 0 0 2 3 2 3 0 0 2 3 2 3 0 0 0 0 3 3 0 0 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 325140

10、867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点汇点源点源点第14页/共70页时间复杂性：时间复杂性： 对顶点进行拓扑排序的时间复杂性为对顶点进行拓扑排序的时间复杂性为O(n+e), 以拓扑排序求以拓扑排序求vei和以拓扑逆序求和以拓扑逆序求vli时时, 所需所需时间均为时间均为O(e), 求各个活动的求各个活动的ek和和lk的时间复的时间复杂度为杂度为O(e), 整个算法的时间复杂性是整个算法的时间复杂性是O(n+e)。第15页/共70页 第五章 图5.1 基本概念5.2 图的存储结构5.3 图的遍历5.4 拓扑排序5.5 关键路径 5.

11、6 最短路径5.7 最小支撑树5.8 图的应用第16页/共70页5.6 最短路径问题 两顶点间可能存在多条路径，每条路径经过的边数不同，每条路径的各边权值之和也不同。 从一个指定的顶点到达另一指定顶点的路径上各边权值之和最小的路径被称为最短路径，这类问题亦称为最短路径问题。 第17页/共70页 单源(由一个指定顶点到其他顶点)最短路径 无权最短路径 正权最短路径 负权最短路径 每对顶点之间的最短路径问题第18页/共70页5.6.1 无权最短路径问题无权所有边的权值都为1源点到各顶点的路径所经历的边的数目就是路径的长度相对于源点由近及远依次求各顶点的最短路径第19页/共70页算法思想：设Di为源

12、点S到顶点 i 的最短路径长度访问初始顶点S，即令DS=0。从S出发，找最短路径为1的顶点，即S的所有邻接顶点w，令Dw=DS+1从上步访问的顶点w出发，找最短路径为2的顶点，即w未被访问的邻接顶点v，令Dv=Dw+1继续上述过程，直至处理完所有顶点。1V12V63V51V32V43V20SV0第20页/共70页V1V6V5V3V4V21122330SV0第21页/共70页上述过程中，访问顶点的次序与对图进行广度优先遍历的次序是一致的;初始时，令Dw=-1，当Dw由-1变成一个正整数时，表示从源点到w的最短路径已求完，Dw值就是最短路径长度,实现时使用数组dist 存储;为了找到最短路径，使用

13、path 存储从源点到顶点 i 的最短路径上最后一个经历的顶点。第22页/共70页算法ShortestPath(v, n)/* 计算从顶点v到其他各顶点的最短路径*/SPath1初始化 CREATQ(Q) . /* 创建一个队列 */ FOR i = 1 TO n DO (pathi -1. disti -1.) distv 0 . Qv. 第23页/共70页SPath2求从顶点v到其他各顶点的最短路径 WHILE NOT(ISEMTQ(Q) DO ( u Q . /* 队头顶点u出队 */ p adjacent (Headu) . /* p为u的边链表的头指针 */ WHILE p DO (

14、 k VerAdj (p) . IF (distk = -1) THEN ( Q k. / 将u的未访问的邻接顶点入队 distk distu + 1. /修改其path值和dist值 pathk u)p link(p) . ) ) 1V12V63V51V32V43V20SV0第24页/共70页 在最短路径的计算中，一个顶点入队出队各一次，时间复杂性为O(n)，而对每个顶点，都要对它的边链表进行遍历，其遍历邻接表的开销为O(e)，于是整个算法的时间复杂性为O(n+e)。 第25页/共70页5.6.2 正权最短路径问题 给定一个带权图D与源点v，求从v到D中其它顶点的最短路径, 限定各边的权值为

15、正实数。 正权最短路径问题不能采用无权最短路径算法。v0v1v2283第26页/共70页 Dijkstra算法思想 按路径长度非递减的次序，逐步产生最短路径的算法，解决正权单源最短路径问题。 首先求出从源点v出发，长度最短的一条最短路径；再参照它求出长度次短的一条最短路径；依此类推，直到求出从顶点v到其它各顶点的最短路径为止。第27页/共70页 把图中所有顶点分成两组，第一组：已求完最短路径的顶点；第二组：未求完最短路径的顶点。按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中。 为了求最短路径，引入辅助数组dist，disti表示当前找到的源点v0到vi的最短路径长度。 初始时： S =

16、 ，dist0=0，disti=+ S V-S第28页/共70页 设S是已求得最短路径的顶点集合，则：下一条最短路径必然是从源点v0出发，中间只经过S中的顶点便可到达的那些顶点vx (vxV-S )的路径中的一条。 每次求最短路径，也就是在V-S中找具有最小dist值的顶点vk，将vk加入集合S，然后对viV-S，修改disti值。 经第一次操作，S=v0，若从源点v0到vi有边，则disti为该边上的权值；若从v0到vi 无边，则disti仍为+ 。 S V-S第29页/共70页 Dijkstra算法描述初始时（S为初始顶点）, Ds=0且 i S，有Di =。在未访问顶点中选择Dv最 小的

17、顶点v ，访问 v ，令 Sv=1。依次考察v的邻接顶点w，若 Dv+weight() Dw ， 则改变Dw的值，使Dw = Dv + weight() 。重复 ，直至所有顶点被访问。 为了找到最短路径，使用path 存储从S到 i 的最短路径上最后一个经历的顶点。第30页/共70页 例 13258102045301202340123402431051 34303 82 254 100 202 44 12第31页/共70页 spathdist0000003421 01325810204530120234在未访问顶点中选择Dv最小的顶点v，访问v，令 Sv=1。依次考察v的邻接顶点w，若 Dv+

18、weight() Dw ，则改变Dw的值，使Dw = Dv + weight() 。重复 ，直至所有顶点被访问。第32页/共70页133023431325810204530120234spathdist10000034210303v0v0第33页/共70页spathdist100010342103028311v0v0v1v132583302343028111325810204530120234第34页/共70页 03421spathdist1100103028311v0 v1v1 v0132581020453012023431241583242311第35页/共70页03421spathdis

19、t1100102315311v0v3v1v3132581020453012023431241583242311第36页/共70页120415813234231131325810204530120234spathdist1100102315311v0v3v1v3第37页/共70页spathdist111110342102315311v0v3v1v3Dijkstra算法算法: 按照非递减顺序依次得到各顶点的最小路按照非递减顺序依次得到各顶点的最小路径长度。径长度。120415813234231131325810204530120234第38页/共70页定理5.4 Dijkstra算法可以按照非递减

20、次序依次得到各顶点的最小路径长度。证明：归纳法算法得到的路径值是各顶点的最小路径长度。算法得到的路径值是按非递减次序得到的。第39页/共70页5.6.3 每对顶点间的最短路径 问题：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求vi 与vj间的最短路径和最短路径长度。 可依次把每个顶点作为源点，执行n次Dijkstra算法。 Floyd算法：定义一个n阶方阵序列： A(-1), A(0), , A(n-1).第40页/共70页 Floyd算法的基本思想：设邻接矩阵存储图，定义初始矩阵A(-1) ij = Edgeij；1、求A(0),即从vi到vj 经由顶点可以是v0的最短

21、路径长度；2、求A(1),即从vi 到vj 经由顶点可以是v0, v1的最短路径长度； n、求A(n-1),即从vi 到vj 经由顶点可以是v0, v1,vn-1的最短路径长度； 其中 A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1 第41页/共70页第42页/共70页第43页/共70页 Floyd算法的时间复杂度为O(n3)，与调用n次Dijkstra算法求每对顶点的最短路径的时间复杂度相同。 但Dijkstra算法仅针对正权图，而Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路；且Floyd算法更

22、简单易于理解。第44页/共70页本章给出的求解最短路径的算法，不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图。第45页/共70页 第五章 图5.1 基本概念5.2 图的存储结构5.3 图的遍历5.4 拓扑排序5.5 关键路径 5.6 最短路径5.7 最小支撑树5.8 图的应用第46页/共70页 5.7 最小支撑树1、基本概念2、生成最小支撑树算法 Prim算法 Kruskar算法第47页/共70页最小支撑树基本概念 对于一个无向网络无向加权连通图N=(V,E,C)(C表示该图为权图)，其顶点个数为|V|=n，图中边的个数为|E| ，我们可以从它的|E

23、|条边中选出n-1条边，使之满足 （1）这n-1条边和图的n个顶点构成一个连通图。 （2）该连通图的代价是所有满足条件(1)的连通图的代价的最小值。 这样的连通图被称为网络的最小支撑树( Minimum-cost Spanning Tree )。 第48页/共70页 最小支撑树的性质l最小支撑树中没有回路 若MST 的边集中有回路，显然可通过去掉回路中某条边而得到花销更小的MSTl最小支撑树是一棵有|V| - 1条边的树l最小支撑树的边集支撑起了图中所有顶点，且边集的代价最小最小支撑树的应用l使连接电路板上一系列接头所需焊接的线路最短l在n个城市间建立造价最低的通讯网络第49页/共70页 5.

24、7 最小支撑树1、基本概念2、生成最小支撑树算法 Prim算法 Kruskar算法第50页/共70页MST性质：N=(V, E, C)是一个连通网，U是V的一个非空子集，若u, v满足weight(u, v)=min weight(u0, v0) | u0U, v0V-U则必存在N的一棵最小支撑树，该支撑树中包括边(u, v)。 uv第51页/共70页1、普里姆(Prim)算法(逐点加入) 设N=(V,E,C)为连通网，TE是N的最小支撑树MST的边的集合，U为MST顶点集。 U=uo(uoV), TE= ； 找到满足weight(u,v)minweight(u1,v1)|u1U, v1V-U

25、, 的边，把它并入TE，同时v并入U； 反复执行 ,直至 V=U , 算法结束。 第52页/共70页4316504535562217 例43165045355622170214316504535562217第53页/共70页4316504535562217 40215021第54页/共70页4053221402154316504535562217 第55页/共70页4105352214316504535562217 4053221第56页/共70页410535221 431650453556221743104535221第57页/共70页 2、克鲁斯卡尔(Kruskar)算法 （逐边加入）设

26、连 通 网 N = ( V, E , C ) ， T 为 N 的 最 小 支 撑 树 。 初 始 时T=V,，即T中没有边，只有n个顶点，也就是n个连通分量。在E中选择权值最小的边，并将此边从E中删除。如果此边的两个顶点在T的不同的连通分量中，则将此边加入到T中，从而导致T中减少一个连通分量;如果此边的两个顶点在同一连通分量中，则重复执行 ，直至T中仅剩一个连通分量时，终止操作。第58页/共70页1 11 10 04 45 53 32 21 10 04 45 53 32 21 12 23 31 10 04 45 53 32 22 21 10 04 43 31 14 45 53 32 22 21 14 43 31 10 04 45 53 35 52 22