离散数学CH04_图论_最短路径与关键路径

离散数学DiscreteMathematics计算机与信息工程学院第4章图论内容提要图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2内容提要欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6定义：设G=(V，E，)为无向简单图，对于每一条边e∈E，均有一个正实数W(e)与之对应，称w为G的权函数，并称G为带有权W的图，又称赋权图，权也称为边的长度。4.5最短路径及关键路径边(vi,vj)的权带权图求给定两点间的最短距离——两点之间的最短路径问题求从某个源点到其余各点的最短路径每一对顶点之间的最短路径4.5最短路径及关键路径求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。v24.5最短路径及关键路径在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：路径长度最短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。4.5最短路径及关键路径其余最短路径的特点：再下一条路径长度次短的最短路径的特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。4.5最短路径及关键路径•从源点到其余各点的最短路径Dijkstra算法（1959）设G有n个顶点；边的长度ℓij≥0；若结点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(i≠1)置vi为T标号，即T=V-P，且d(vi)=W(v1,vi)若viadjvid(vi)=∞else4.5最短路径及关键路径Step2:找最小寻找具有最小值的T标号的结点。若为vl，则将vl的T标号改为P标号，且P=P∪{vl}，T=T-{vl}。Step3：修改修改与vl相邻的结点的T标号的值。viT：d(vi)=d(vl)+W(vl,vi)若d(vl)+W(vl,vi)d(vi)d(vi)否则4.5最短路径及关键路径Step4：重复（2）和（3），直到vn改为P标号为止。【例】试求无向赋权图中v1到v6的最短路径。v2v47512v1v3v5v6412364.5最短路径及关键路径1(v1)∞∞∞04(v1)P={v1}T={v2,v3,v4,v5,v6}4.5最短路径及关键路径P={v1,v2}T={v3,v4,v5,v6}(v1)∞03(v1,v2)18(v1,v2)6(v1,v2)4.5最短路径及关键路径P={v1,v2,v3}T={v4,v5,v6}(v1)∞0(v1,v2)18(v1,v2)4(v1,v2,v3)34.5最短路径及关键路径P={v1,v2,v3,v5}T={v4,v6}(v1)0(v1,v2)17(v1,v2,v3,v5)(v1,v2,v3)3410(v1,v2,v3,v5)4.5最短路径及关键路径P={v1,v2,v3,v5,v4}T={v6}(v1)0(v1,v2)1(v1,v2,v3,v5)(v1,v2,v3)349(v1,v2,v3,v5)74.5最短路径及关键路径(v1)0(v1,v2)P={v1,v2,v3,v5v4,v6}T={}1(v1,v2,v3,v5)(v1,v2,v3)34(v1,v2,v3,v5,v4)794.5最短路径及关键路径10(v5)第1短V1V5V4V2V3V610101002050205030510v2v3v4v5v6step1503010010∞20(v4)第2短step2503020∞30(v3)第3短step34030∞35(v2)第4短step4355045(v6)第5短step545/V1/V5/V1/V3/V24.5最短路径及关键路径2(v2)第1短v2v3v4v5v6v7step1253∞∞3(v4)第2短step243∞4(v3)第3短step384∞7(v5)第4短step4798(v6)第5短step58V2V12V3V6V7V4V553125753517step613(v7)第6短13∞∞∞99144.5最短路径及关键路径试用Dijkstra算法求下列简单无向赋权图中V1到V11的最短路径。4.5最短路径及关键路径v1v2v5v4v10v8v7v11v3v6v92112919465397243116827——求任意两点间最短距离的Floyd算法基本思想：从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。4.5最短路径及关键路径求每一对顶点之间的最短路径在实施一个工程计划时，若将整个工程分成若干工序，有些工序可以同时实施，有些工序必须在完成另一些工序后才能实施，工序之间的次序关系可以用有向图来表示，这种有向图称为PERT图。4.5最短路径及关键路径关键路径问题——PERT图（计划评审技术图）,,,DVEVv定义：设为一个有向图称{|}(,)DxvxVvxEv为的后继元集；{|}(,)DxvxVxvEv为的先驱元集.4.5最短路径及关键路径关键路径问题——PERT图（计划评审技术图）,,DVEWn设是一个阶有向带权图，满足(1)(2)(3)0,0(4,)ijijDDvwv是简单图；中无回路；有一个顶点入度为称此顶点为始点；有一个顶点出度为，称此顶点为终点；记边带的，它一般权为表示时间；PERTD则称为图.4.5最短路径及关键路径关键路径问题——PERT图（计划评审技术图）在PERT图中求关键路径，就是从始点到终点的一条最长路径，通过求各顶点的最早完成时间来求关键路径。4.5最短路径及关键路径关键路径问题——PERT图（计划评审技术图）PERT图——最早完成时间1()v自始点记为开始沿最长路径（按权计算）iivv到达所需的时间，称为的最早完成时间.(),1,2,...,.iTEvin记作11()0,()iTEvvi显然有的最早完成时间可按如下公式计算：()()max{()},2,3,...,.jDivviiijTEvTEvwin1()nnnvTEvvv终点的最早完成时间就是从到的最长路径的权。a（7）4.5最短路径及关键路径PERT图——最晚完成时间()()nniTLvTEvinv由定义可知，；的最晚完成时间由下时，面公式计算：()()max{()},1,2,3,...,1.jDiiiijvvTLvTLvwin1().niiivvvvTLv在保证终点的最早完成时间不增加的条件下，自最迟到达的时间称为的最晚完成时间，记作b（7）4.5最短路径及关键路径PERT图——缓冲时间0,()()()()iiiiiTLvTEvLTEvvTv。称为由定义可知的缓冲时间，()()(),1,2,...,.iiiTSvTLvTEvin记作0.tt在关键路径上，任何工序如果耽误了时间，整个工序就耽误了时间，因而在关键路径上各顶点的缓冲时间均为4.5最短路径及关键路径PERT图举例例求图中所示的PERT图中各顶点的最早、最晚和缓冲时间以及关键路径。4.5最短路径及关键路径解：各点最早完成时间用公式(7a)计算：3412()0;()max{01}1;()max{02,10}2;()max{03,22}4;TEvTEvTEvTEv5678()max{13,44}8;()max{24,81}9;()max{14,24}6;()max{91,66}12.TEvTEvTEvTEv4.5最短路径及关键路径b各点最晚完成时间用公式(7)计算：7865()12;()min{126}6;()min{121}11;()min{111}10;TLvTLvTLvTLv4321()min{104}6;()min{62,114,64}2;()min{20,103,64}2;()min{21,22,63}0.TLvTLvTLvTLv4.5最短路径及关键路径计算各点缓冲时间：13782456()()()()0;()211;()642;()1082;()1192.TSvTSvTSvTSvTSvTSvTSvTSv1378.vvvv关键路径为4.5最短路径及关键路径