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

1、离散数学离散数学Discrete Mathematics计算机与信息工程学院计算机与信息工程学院第第4章章 图图 论论内容提要内容提要图的根本概念图的根本概念4.1连通图连通图4.34.4图的矩阵表示图的矩阵表示路和回路路和回路4.2内容提要内容提要欧拉图和哈密顿图欧拉图和哈密顿图4.5二部图及匹配二部图及匹配4.74.8平面图平面图树树4.6n定义：定义：n设设G=(VG=(V，E E，) )为无向简单图，对于每一条边为无向简单图，对于每一条边eEeE，均，均有一个正实数有一个正实数W(e)W(e)与之对应，称与之对应，称w w为为GG的权函数，并称的权函数，并称GG为为带有权带有权WW的图

2、，又称赋权图，权也称为边的长度。的图，又称赋权图，权也称为边的长度。4.5 4.5 最短途径及关键途径最短途径及关键途径边边(vi,vj)的的权权带权图带权图求给定两点间的最短间隔求给定两点间的最短间隔两点之间的最短途径问题两点之间的最短途径问题 求从某个源点到其他各点的最短途径每一对顶点之间的最短途径每一对顶点之间的最短途径4.5 4.5 最短途径及关键途径最短途径及关键途径 求从源点到其他各点的最短途径的算法的根本思想求从源点到其他各点的最短途径的算法的根本思想: :依最短途径的长度递增的次序求得各条途径依最短途径的长度递增的次序求得各条途径源点源点v1其中，从源点到顶点v1的最短途径是一

3、切最短途径中长度最短者。v24.5 4.5 最短途径及关键途径最短途径及关键途径在这条途径上，必定只含一条弧，并且这条弧的权值最小。 下一条途径长度次短的最短途径的特点：途径长度最短的最短途径的特点： 它只能够有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。4.5 4.5 最短途径及关键途径最短途径及关键途径其他最短途径的特点：再下一条途径长度次短的最短途径的特点:它能够有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点

4、到该点(只含一条弧)； 或者是从源点经过已求得最短途径的顶点，再到达该顶点。4.5 4.5 最短途径及关键途径最短途径及关键途径 从源点到其他各点的最短途径从源点到其他各点的最短途径 Dijkstra算法算法1959 设设G有有n个顶点；边的长度个顶点；边的长度ij0；假设结点；假设结点vi和和vj没有边相连没有边相连(不是邻接点不是邻接点)，那么令，那么令ij=，对，对每个结点每个结点vi，令，令ij=0。4.5 4.5 最短途径及关键途径最短途径及关键途径 将顶点集将顶点集V V分成两部分，一部分成为具有分成两部分，一部分成为具有P P永久性永久性标号的集合，另一部分成为具有标号的集合，另

5、一部分成为具有T T暂时性标号的集合。暂时性标号的集合。所谓结点所谓结点v v的的P P标号是指从标号是指从v1v1到到v v的最短途径的长度；而顶点的最短途径的长度；而顶点u u的的T T标号是指从标号是指从v1v1到到u u某条途径的长度。某条途径的长度。 Dijkstras Dijkstras算法首算法首先将先将v1v1取为取为P P标号，其他结点取为标号，其他结点取为T T标号，然后逐渐将具有标号，然后逐渐将具有T T标号的结点改为标号的结点改为P P标号。当结点标号。当结点vnvn已被改为已被改为P P标号时，就找标号时，就找到了一条从到了一条从v1v1到到vnvn的最短途径。的最短

6、途径。4.5 4.5 最短途径及关键途径最短途径及关键途径DijkstrasDijkstras根本思绪：根本思绪：nStep1:Step1:n初始化：将初始化：将v1v1置为置为P P标号，标号，d(v1)=0d(v1)=0，P=v1P=v1，vi(i1)vi(i1)置置vi vi 为为T T标号，即标号，即T=V-PT=V-P，且，且n d(vi)=W(v1, vi) d(vi)=W(v1, vi) 假设假设viadjviviadjvin d(vi)= else d(vi)= else4.5 4.5 最短途径及关键途径最短途径及关键途径nStep2:Step2:找最小找最小n寻觅具有最小值的

7、寻觅具有最小值的T T标号的结点。假设为标号的结点。假设为vlvl，那么将，那么将vlvl的的T T标标号改为号改为P P标号，且标号，且P=PvlP=Pvl，T=T-vlT=T-vl。nStep3Step3：修正：修正n修正与修正与vl vl 相邻的结点的相邻的结点的T T标号的值。标号的值。n viviT T ： n n d(vi)= d(vi)=d(vl)+W(vl,vi) 假设假设d(vl)+W(vl,vi)d(vi)d(vi) 否那么否那么4.5 4.5 最短途径及关键途径最短途径及关键途径n Step4：反复：反复2和和3，直到，直到vn改为改为P标号为止。标号为止。n 【例】试求

8、无向赋权图中【例】试求无向赋权图中v1到到v6的最短途径。的最短途径。 v2v47512v1v3v5v6412364.5 4.5 最短途径及关键途径最短途径及关键途径1(v1)04(v1)P=v1T=v2 , v3,v4,v5,v64.5 4.5 最短途径及关键途径最短途径及关键途径P=v1,v2T=v3,v4,v5,v6(v1)03(v1,v2)18(v1,v2)6(v1,v2)4.5 4.5 最短途径及关键途径最短途径及关键途径P=v1,v2 , v3T=v4,v5,v6(v1)0(v1,v2)18(v1,v2)4(v1,v2, v3)34.5 4.5 最短途径及关键途径最短途径及关键途径

9、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 最短途径及关键途径最短途径及关键途径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 最短途径及关键途径最短途径及关键途径(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

10、.5 4.5 最短途径及关键途径最短途径及关键途径10(v5)第第1短短V1V5V4V2V3V610101002050205030510v2 v3 v4 v5 v6step150 30 100 1020(v4)第第2短短step250 30 2030(v3)第第3短短step340 3035(v2)第第4短短step4355045(v6)第第5短短step545/V1/V5/V1/V3/V24.5 4.5 最短途径及关键途径最短途径及关键途径2(v2)第第1短短v2 v3 v4 v5 v6 v7step1253 3(v4)第第2短短step2434(v3)第第3短短step3847(v5)第第

11、4短短step4798(v6)第第5短短step58V2V12V3V6V7V4V553125753517step613(v7)第第6短短1399144.5 4.5 最短途径及关键途径最短途径及关键途径n试用试用DijkstraDijkstra算法求以下简单无向赋权图中算法求以下简单无向赋权图中nV1V1到到V11V11的最短途径。的最短途径。n 4.5 4.5 最短途径及关键途径最短途径及关键途径v1 v2v5v4v10v8v7v11v3v6v92112919465397243116827 求恣意两点间最短间隔的求恣意两点间最短间隔的FloydFloyd算法算法根本思想：根本思想：从从 vi

12、vi 到到 vj vj 的一切能够存在的途径中，选出一条长度最的一切能够存在的途径中，选出一条长度最 短的途径。短的途径。4.5 4.5 最短途径及关键途径最短途径及关键途径求每一对顶点之间的最短途径在实施一个工程方案时，假设将整个工程分成假在实施一个工程方案时，假设将整个工程分成假设干工序，有些工序可以同时实施，有些工序必设干工序，有些工序可以同时实施，有些工序必需在完成另一些工序后才干实施，工序之间的次需在完成另一些工序后才干实施，工序之间的次序关系可以用有向图来表示，这种有向图称为序关系可以用有向图来表示，这种有向图称为PERTPERT图。图。4.5 4.5 最短途径及关键途径最短途径及

13、关键途径关键途径问题关键途径问题PERTPERT图方案评审技术图图方案评审技术图,DV EVv定义：设为一个有向图称 |(,)DxvxVv xE v为 的后继元集； |(,)DxvxVx vE v为 的先驱元集.4.5 4.5 最短途径及关键途径最短途径及关键途径关键途径问题关键途径问题PERTPERT图方案评审技术图图方案评审技术图,DV E Wn设是一个 阶有向带权图，满足(1)(2)(3)0,0(4,)ijijDDvwv是简单图；中无回路；有一个顶点入度为 称此顶点为始点； 有一个顶点出度为 ，称此顶点为终点；记边带的，它一般权为表示时间；PERTD则称 为图.4.5 4.5 最短途径及

14、关键途径最短途径及关键途径关键途径问题关键途径问题PERTPERT图方案评审技术图图方案评审技术图在在PERTPERT图中求关键途径，就是从始点到终点的图中求关键途径，就是从始点到终点的一条最长途径，经过求各顶点的最早完成时间来一条最长途径，经过求各顶点的最早完成时间来求关键途径。求关键途径。4.5 4.5 最短途径及关键途径最短途径及关键途径关键途径问题关键途径问题PERTPERT图方案评审技术图图方案评审技术图PERTPERT图图最早完成时间最早完成时间1()v自始点 记为开始沿最长路径（按权计算）iivv到达 所需的时间，称为 的最早完成时间.( ),1,2,., .iTE vin记作1

15、1( )0,()iTE vv i 显然有的最早完成时间可按如下公式计算：()( )max ( ),2,3,., .jDivviiijTE vTE vwin1()nnnvTE vvv终点 的最早完成时间就是从 到 的最长路径的权。a（7 ）4.5 4.5 最短途径及关键途径最短途径及关键途径PERTPERT图图最晚完成时间最晚完成时间()()nniTL vTE vinv由定义可知，；的最晚完成时间由下时，面公式计算：()( )max ( ),1,2,3,.,1.jDiiiijvvTL vTL vwin1( ).niiivvvvTL v在保证终点 的最早完成时间不增加的条件下，自最迟到达 的时间称

16、为 的最晚完成时间，记作b（7 ）4.5 4.5 最短途径及关键途径最短途径及关键途径PERTPERT图图缓冲时间缓冲时间0,( )( )( )( )iiiiiTL vTE vLTE vvTv 。称为 由定义可知的缓冲时间，( )( )( ),1,2,., .iiiTS vTL vTE vin记作0.tt在关键路径上，任何工序如果耽误了时间，整个工序就耽误了时间，因而在关键路径上各顶点的缓冲时间均为4.5 4.5 最短途径及关键途径最短途径及关键途径PERTPERT图举例图举例例例 求图中所示的求图中所示的PERTPERT图中各顶点的最早、最晚和缓冲图中各顶点的最早、最晚和缓冲时间以及关键途径。时间以及关键途径。4.5 4.5 最短途径及关键途径最短途径及关键途径解：各点最早完成时间用公式(7a)计算：3412( )0;()max0 11;()max02,1 02;()max03,224;TE vTE vTE vTE v5678()max1 3,448;()max24,8 19;()max14,246;()max9 1,6612.TE vTE vTE vTE v4.5 4.5 最短途径及关键途径最短途径及关键途径b各点最晚完成时间用公式(7 )计算：7865()12;()min1266;()min12 111;