离散数学CH图论最短路径与关键路径省公共课一等奖全国赛课获奖课件.pptx

离散数学离散数学Discrete Mathematics计算机与信息工程学院计算机与信息工程学院第第4章章 图图 论论第1页内容提要内容提要图基本概念图基本概念4.1连通图连通图4.34.4图矩阵表示图矩阵表示路和回路路和回路4.2第2页内容提要内容提要欧拉图和哈密顿图欧拉图和哈密顿图4.5二部图及匹配二部图及匹配4.74.8平面图平面图树树4.6第3页n定义：定义：设设G=(VG=(V，E E，)为无向简单图，对于每一条边为无向简单图，对于每一条边eEeE，都有一，都有一个正实数个正实数W(e)W(e)与之对应，称与之对应，称w w为为GG权函数，并称权函数，并称GG为带有权为带有权WW图，又称赋权图，权也称为边长度。图，又称赋权图，权也称为边长度。4.5 4.5 最短路径及关键路径最短路径及关键路径边边(vi,vj)权权带权图带权图第4页求给定两点间最短距离求给定两点间最短距离两点之间最短路径问题两点之间最短路径问题 求从某个源点到其余各点最短路径求从某个源点到其余各点最短路径每一对顶点之间最短路径每一对顶点之间最短路径4.5 4.5 最短路径及关键路径最短路径及关键路径第5页 求求从源点到其余各点最短路径从源点到其余各点最短路径算法基本思想算法基本思想:依最短路径长度递增次序求得各条路径依最短路径长度递增次序求得各条路径源点源点v1其中，从源点到顶点从源点到顶点v v1 1最最短路径短路径是全部最短路径中长度最短者。v24.5 4.5 最短路径及关键路径最短路径及关键路径第6页在这条路径上，必定只含一条弧，而且这条弧权值最小。下一条路径长度次短最短路径特点：路径长度最短最短路径最短路径特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再抵达该顶点(由两条弧组成)。4.5 4.5 最短路径及关键路径最短路径及关键路径第7页其余最短路径特点：再下一条路径长度次短最短路径最短路径特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再抵达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再抵达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径顶点，再抵达该顶点。4.5 4.5 最短路径及关键路径最短路径及关键路径第8页从源点到其余各点最短路径从源点到其余各点最短路径 Dijkstra Dijkstra算法算法（19591959）设设G G有有n n个顶点；边长度个顶点；边长度ij0ij0；若结点；若结点vivi和和vjvj没没有边相连有边相连(不是邻接点不是邻接点)，则令，则令ij=ij=，对每个结，对每个结点点vivi，令，令ij=0ij=0。4.5 4.5 最短路径及关键路径最短路径及关键路径第9页 将顶点集将顶点集V V分成两部分，一部分成为含有分成两部分，一部分成为含有P P（永久性）标（永久性）标号集合，另一部分成为含有号集合，另一部分成为含有T T（暂时性）标号集合。所谓结（暂时性）标号集合。所谓结点点v vP P标号是指从标号是指从v1v1到到v v最短路径长度；而顶点最短路径长度；而顶点u uT T标号是指从标号是指从v1v1到到u u某条路径长度。某条路径长度。Dijkstras算法首先将算法首先将v1v1取为取为P P标号，标号，其余结点取为其余结点取为T T标号，然后逐步将含有标号，然后逐步将含有T T标号结点改为标号结点改为P P标号。标号。当结点当结点vnvn已被改为已被改为P P标号时，就找到了一条从标号时，就找到了一条从v1v1到到vnvn最短路最短路径。径。4.5 4.5 最短路径及关键路径最短路径及关键路径DijkstrasDijkstras基本思绪：基本思绪：第10页nStep1:Step1:初始化：将初始化：将v v1 1置为置为P P标号，标号，d(vd(v1 1)=0)=0，P=vP=v1 1，v vi i(i1)(i1)置置v vi i 为为T T标号，即标号，即T=V-PT=V-P，且，且 d(vd(vi i)=W(v)=W(v1 1,v,vi i)若若v vi iadjvadjvi i d(v d(vi i)=else)=else4.5 4.5 最短路径及关键路径最短路径及关键路径第11页nStep2:Step2:找最小找最小寻找含有最小值寻找含有最小值T T标号结点。若为标号结点。若为v vl l，则将，则将v vl lT T标号改为标号改为P P标号，标号，且且P=PvP=Pvl l，T=T-vT=T-vl l。nStep3Step3：修改：修改修改与修改与vlvl 相邻结点相邻结点T T标号值。标号值。vivi T T：d(vi)=d(vi)=d(vl)+W(vl,vi)若若d(vl)+W(vl,vi)d(vi)d(vi)不然不然4.5 4.5 最短路径及关键路径最短路径及关键路径第12页nStep4：重复（重复（2 2）和（）和（3 3），直到），直到v vn n改为改为P P标号为止。标号为止。【例例】试求无向赋权图中试求无向赋权图中v v1 1到到v v6 6最短路径。最短路径。v2v47512v1v3v5v6412364.5 4.5 最短路径及关键路径最短路径及关键路径第13页1(v1)04(v1)P=v1T=v2,v3,v4,v5,v64.5 4.5 最短路径及关键路径最短路径及关键路径第14页P=v1,v2T=v3,v4,v5,v6(v1)03(v1,v2)18(v1,v2)6(v1,v2)4.5 4.5 最短路径及关键路径最短路径及关键路径第15页P=v1,v2,v3T=v4,v5,v6(v1)0(v1,v2)18(v1,v2)4(v1,v2,v3)34.5 4.5 最短路径及关键路径最短路径及关键路径第16页P=v1,v2,v3,v5T=v4,v6(v1)0(v1,v2)17(v1,v2,v3,v5)(v1,v2,v3)3410(v1,v2,v3,v5)4.5 4.5 最短路径及关键路径最短路径及关键路径第17页P=v1,v2,v3,v5,v4T=v6(v1)0(v1,v2)1(v1,v2,v3,v5)(v1,v2,v3)349(v1,v2,v3,v5)74.5 4.5 最短路径及关键路径最短路径及关键路径第18页(v1)0(v1,v2)P=v1,v2,v3,v5 v4,v6T=1(v1,v2,v3,v5)(v1,v2,v3)34(v1,v2,v3,v5,v4)794.5 4.5 最短路径及关键路径最短路径及关键路径第19页10(v5)第第1短短V1V5V4V2V3V610101002050205030510v2 v3 v4 v5 v6step150 30 100 1020(v4)第第2 2短短step250 30 2030(v3)第第3短短step340 3035(v2)第第4短短step4355045(v6)第第5短短step545/V1/V5/V1/V3/V24.5 4.5 最短路径及关键路径最短路径及关键路径第20页2(v2)第第1短短v2 v3 v4 v5 v6 v7step1253 3(v4)第第2 2短短step2434(v3)第第3短短step3847(v5)第第4短短step4798(v6)第第5短短step58V2V12V3V6V7V4V553125753517step613(v7)第第6短短1399144.5 4.5 最短路径及关键路径最短路径及关键路径第21页n试用试用DijkstraDijkstra算法求以下简单无向赋权图中算法求以下简单无向赋权图中V1V1到到V11V11最短路径。最短路径。4.5 4.5 最短路径及关键路径最短路径及关键路径v1 v2v5v4v10v8v7v11v3v6v92112919465397243116827第22页 求任意两点间最短距离求任意两点间最短距离FloydFloyd算法算法基本思想：从 vi 到 vj 全部可能存在路径中，选出一条长度最 短路径。4.5 4.5 最短路径及关键路径最短路径及关键路径求每一对顶点之间最短路径第23页在实施一个工程计划时，若将整个工程分成若干在实施一个工程计划时，若将整个工程分成若干工序，有些工序能够同时实施，有些工序必须在工序，有些工序能够同时实施，有些工序必须在完成另一些工序后才能实施，工序之间次序关系完成另一些工序后才能实施，工序之间次序关系能够用有向图来表示，这种有向图称为能够用有向图来表示，这种有向图称为PERTPERT图。图。4.5 4.5 最短路径及关键路径最短路径及关键路径关键路径问题关键路径问题PERTPERT图（计划评审技术图）图（计划评审技术图）第24页4.5 4.5 最短路径及关键路径最短路径及关键路径关键路径问题关键路径问题PERTPERT图（计划评审技术图）图（计划评审技术图）第25页4.5 4.5 最短路径及关键路径最短路径及关键路径关键路径问题关键路径问题PERTPERT图（计划评审技术图）图（计划评审技术图）第26页在在PERTPERT图中求关键路径，就是从始点到终点一图中求关键路径，就是从始点到终点一条最长路径，经过求各顶点最早完成时间来条最长路径，经过求各顶点最早完成时间来求关键路径。求关键路径。4.5 4.5 最短路径及关键路径最短路径及关键路径关键路径问题关键路径问题PERTPERT图（计划评审技术图）图（计划评审技术图）第27页PERTPERT图图最早完成时间最早完成时间4.5 4.5 最短路径及关键路径最短路径及关键路径第28页PERTPERT图图最晚完成时间最晚完成时间4.5 4.5 最短路径及关键路径最短路径及关键路径第29页PERTPERT图图缓冲时间缓冲时间4.5 4.5 最短路径及关键路径最短路径及关键路径第30页PERTPERT图举例图举例例例 求图中所表示求图中所表示PERTPERT图中各顶点最早、最晚和缓冲时图中各顶点最早、最晚和缓冲时间以及关键路径。间以及关键路径。4.5 4.5 最短路径及关键路径最短路径及关键路径第31页4.5 4.5 最短路径及关键路径最短路径及关键路径第32页4.5 4.5 最短路径及关键路径最短路径及关键路径第33页4.5 4.5 最短路径及关键路径最短路径及关键路径第34页第35页