离散数学CH04图论最短路径与关键路径.ppt

离散数学 Discrete Mathematics,计算机与信息工程学院,第4章 图 论,内容提要,图的基本概念,4.1,连通图,4.3,4.4,图的矩阵表示,路和回路,4.2,内容提要,欧拉图和哈密顿图,4.5,二部图及匹配,4.7,4.8,平面图,树,4.6,定义： 设G=(V，E，)为无向简单图，对于每一条边eE，均有一个正实数W(e)与之对应，称w为G的权函数，并称G为带有权W的图，又称赋权图，权也称为边的长度。,4.5 最短路径及关键路径,边(vi,vj)的权,带权图,求给定两点间的最短距离 两点之间的最短路径问题,求从某个源点到其余各点的最短路径,每一对顶点之间的最短路径,4.5 最短路径及关键路径,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。,v2,4.5 最短路径及关键路径,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的最短路径的特点：,路径长度最短的最短路径的特点：,它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。,4.5 最短路径及关键路径,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。,4.5 最短路径及关键路径,从源点到其余各点的最短路径 Dijkstra算法（1959） 设G有n个顶点；边的长度ij0；若结点vi和vj没有边相连(不是邻接点)，则令ij=，对每个结点vi，令ij=0。,4.5 最短路径及关键路径,将顶点集V分成两部分，一部分成为具有P（永久性）标号的集合，另一部分成为具有T（暂时性）标号的集合。所谓结点v的P标号是指从v1到v的最短路径的长度；而顶点u的T标号是指从v1到u某条路径的长度。 Dijkstras算法首先将v1取为P标号，其余结点取为T标号，然后逐步将具有T标号的结点改为P标号。当结点vn已被改为P标号时，就找到了一条从v1到vn的最短路径。,4.5 最短路径及关键路径,Dijkstras基本思路：,Step1: 初始化：将v1置为P标号，d(v1)=0，P=v1，vi(i1)置vi 为T标号，即T=V-P，且 d(vi)=W(v1, vi) 若viadjvi d(vi)= else,4.5 最短路径及关键路径,Step2:找最小 寻找具有最小值的T标号的结点。若为vl，则将vl的T标号改为P标号，且P=Pvl，T=T-vl。 Step3：修改 修改与vl 相邻的结点的T标号的值。 viT ： d(vi)=,4.5 最短路径及关键路径,Step4：重复（2）和（3），直到vn改为P标号为止。 【例】试求无向赋权图中v1到v6的最短路径。,4.5 最短路径及关键路径,P=v1 T=v2 , v3,v4,v5,v6,4.5 最短路径及关键路径,P=v1,v2 T=v3,v4,v5,v6,4.5 最短路径及关键路径,P=v1,v2 , v3 T=v4,v5,v6,4.5 最短路径及关键路径,P=v1,v2 , v3, v5 T=v4,v6,4.5 最短路径及关键路径,P=v1,v2 , v3, v5 , v4 T=v6,4.5 最短路径及关键路径,(v1),0,(v1,v2),P=v1,v2 , v3, v5 v4 , v6 T=,1,(v1,v2 ,v3,v5),(v1,v2, v3),3,4,(v1,v2 ,v3,v5 ,v4),7,9,4.5 最短路径及关键路径,10(v5)第1短,step1,50,30,100,10,20(v4)第2短,step2,50,30,20,30(v3)第3短,step3,40,30,35(v2)第4短,step4,35,50,45(v6)第5短,step5,45,/V1,/V5,/V1,/V3,/V2,4.5 最短路径及关键路径,2(v2)第1短,step1,2,5,3,3(v4)第2短,step2,4,3,4(v3)第3短,step3,8,4,7(v5)第4短,step4,7,9,8(v6)第5短,step5,8,step6,13(v7)第6短,13,9,9,14,4.5 最短路径及关键路径,试用Dijkstra算法求下列简单无向赋权图中 V1到V11的最短路径。,4.5 最短路径及关键路径,求任意两点间最短距离的Floyd算法 基本思想： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最 短的路径。,4.5 最短路径及关键路径,求每一对顶点之间的最短路径,在实施一个工程计划时，若将整个工程分成若干工序，有些工序可以同时实施，有些工序必须在完成另一些工序后才能实施，工序之间的次序关系可以用有向图来表示，这种有向图称为PERT图。,4.5 最短路径及关键路径,关键路径问题PERT图（计划评审技术图）,4.5 最短路径及关键路径,关键路径问题PERT图（计划评审技术图）,4.5 最短路径及关键路径,关键路径问题PERT图（计划评审技术图）,在PERT图中求关键路径，就是从始点到终点的一条最长路径，通过求各顶点的最早完成时间来 求关键路径。,4.5 最短路径及关键路径,关键路径问题PERT图（计划评审技术图）,PERT图最早完成时间,4.5 最短路径及关键路径,PERT图最晚完成时间,4.5 最短路径及关键路径,PERT图缓冲时间,4