离散数学PPT课件-4最短路径与关键路径.ppt

4.带权图的最短路与关键路在实际应用中在实际应用中,一些图的边上标有数字一些图的边上标有数字,用以表示两结点用以表示两结点间的距离、或路费等等间的距离、或路费等等.然后求两点间的最短路径然后求两点间的最短路径.这是这是很有意义的问题很有意义的问题.一一.带权图带权图(赋权图赋权图)1.定义定义:设设G=,是个图是个图,如果如果G的每条边的每条边e上都标有上都标有实数实数c(e)(c(e)W),称这个数为边称这个数为边e的权的权,称此图为称此图为带权图带权图.规定规定:u,vV,边边(u,v)的权记作的权记作 c(u,v)1)c(u,u)=0 2)如果结点如果结点u与与v之间无边相连之间无边相连,则则 c(u,v)=2.带权图的路长带权图的路长:结点结点u与与v之间的路长是指该路所包含的之间的路长是指该路所包含的各边权的总和各边权的总和.例如右图中例如右图中v1 v2v3 v6 的路长为的路长为12.3.带权图的两点间距离带权图的两点间距离:结点结点u与与v之间的之间的 最短路的长最短路的长称为结点称为结点u与与v之间的距离之间的距离.记作记作d(u,v).如果如果G是有向带权图是有向带权图,称为结点称为结点u到到v的距离的距离,记作记作d 例如上图中例如上图中 d(v2,v5)=24.带权图中求一个结点到各点的最短路的算法带权图中求一个结点到各点的最短路的算法:此算法是于此算法是于1959年由年由E.W.Dijkstra提出的提出的.基本思想基本思想:若使若使(u0,u1,u2,un-1,un)最短最短,就要使就要使(u0,u1,u2,un-1)最短最短,即保证从即保证从u0到以后各点的路都是到以后各点的路都是最最短的短的.v6 v5 v4v1 v3 v2365112336令图令图G=,集合集合Si V Si=V-Si,令令|V|=n Si=u|从从u0到到u的最短路已求出的最短路已求出 Si=u|从从u0到到u的最短路未求出的最短路未求出Dijkstra算法算法:(求从求从u0到各点到各点u的最短路长的最短路长)第一步第一步.置初值置初值:d(u0,u0)=0 d(u0,v)=(其中其中v u0)i=0 S0=u0 第二步第二步.若若 i=n-1 则停则停.否则转第三步否则转第三步第三步第三步.对每个对每个uSi 计算计算 d(u0,u)=mind(u0,u),d(u0,ui)+c(ui,u)计算计算 mind(u0,u)并用并用ui+1记下达到该最小值的那个结点记下达到该最小值的那个结点u 置置Si+1=Siui+1 i=i+1 转第二步转第二步.ui SiuSi例例.求右图中从求右图中从v1到到v6的的最短路最短路1.置初值置初值:u0=v1 d(u0,u0)=0 d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=2.3.i=0 S0=v1 S0=v2,v3,v4,v5,v6 d(u0,v2)=mind(u0,v2),d(u0,u0)+c(u0,v2)=min,0+3=3 d(u0,v3)=mind(u0,v3),d(u0,u0)+c(u0,v3)=min,0+=d(u0,v4)=mind(u0,v4),d(u0,u0)+c(u0,v4)=min,0+5=5 d(u0,v5)=mind(u0,v5),d(u0,u0)+c(u0,v5)=min,0+=d(u0,v6)=mind(u0,v6),d(u0,u0)+c(u0,v6)=min,0+=min3,5,=3 ui+1=u1=v2,实际已求出实际已求出d(u0,v2)=3,路是路是u0v2 v6 v5 v4v1 v3 v2365113336i=1 S1=v1,v2 S1=v3,v4,v5,v6 u1=v2 d(u0,u1)=3 d(u0,v3)=mind(u0,v3),d(u0,u1)+c(u1,v3)=min,3+6=9 d(u0,v4)=mind(u0,v4),d(u0,u1)+c(u1,v4)=min5,3+1=4 d(u0,v5)=mind(u0,v5),d(u0,u1)+c(u1,v5)=min,3+=d(u0,v6)=mind(u0,v6),d(u0,u1)+c(u1,v6)=min,3+=min9,4,=4 ui+1=u2=v4,实际已求出实际已求出d(u0,v4)=4,路是路是u0v2v4 v6 v5 v4v1 v3 v2365113336i=2 S2=v1,v2,v4 S2=v3,v5,v6 u2=v4 d(u0,u2)=4d(u0,v3)=mind(u0,v3),d(u0,u2)+c(u2,v3)=min9,4+3=7d(u0,v5)=mind(u0,v5),d(u0,u2)+c(u2,v5)=min,4+1=5d(u0,v6)=mind(u0,v6),d(u0,u2)+c(u2,v6)=min,4+=min7,5,=5 ui+1=u3=v5,实际已求出实际已求出d(u0,v5)=5,路是路是u0v2v4 v5 v6 v5 v4v1 v3 v2365113336i=3 S3=v1,v2,v4,v5 S3=v3,v6 u3=v5 d(u0,u3)=5 d(u0,v3)=mind(u0,v3),d(u0,u3)+c(u3,v3)=min7,5+3=7 d(u0,v6)=mind(u0,v6),d(u0,u3)+c(u3,v6)=min,5+6=11 min7,11=7 ui+1=u4=v3,实际已求出实际已求出d(u0,v3)=7,路是路是u0v2v4 v3i=4 S3=v1,v2,v4,v5,v3 S3=v6 u4=v3 d(u0,u4)=7d(u0,v6)=mind(u0,v6),d(u0,u4)+c(u4,v6)=min11,7+3=10 min10=10 ui+1=u5=v6,实际已求出实际已求出d(u0,v6)=10,路是路是u0v2v4 v3 v6i=5(n-1)时时 算法停止算法停止.v6 v5 v4v1 v3 v2365113336二二.求关键路径问题求关键路径问题 实施一项工程计划时实施一项工程计划时,若将整个工程分成若干个工序若将整个工程分成若干个工序,有些工序可以同时实施有些工序可以同时实施,有些工序必须在另一些工序完成有些工序必须在另一些工序完成之后才能实施之后才能实施,工序之间的次序关系用有带权的向图表工序之间的次序关系用有带权的向图表示示,这种有向图称为这种有向图称为PERT图图(计划评审技术图计划评审技术图).(Program Evaluation and Review Technique)1.PERT图定义图定义:D=是有向带权图是有向带权图,|V|=n,如果满足如果满足:(1).D是简单图是简单图.(2).D中无回路中无回路.(3).有一个结点入度为有一个结点入度为0,称此结点为称此结点为发点发点;有一个结点有一个结点出度为出度为0,称此称此 结点为结点为收点收点.(4).边边带的权记作带的权记作wij,通常表示时间通常表示时间.称此图称此图D为为PERT图图.如右图就是个如右图就是个PERT图图.在在PERT图中只要是图中只要是找出关键路径找出关键路径,即是影响即是影响工程工期的关键路径工程工期的关键路径.就是通过求从发点到收点就是通过求从发点到收点的一条最长路径的一条最长路径,通过求各个结点的最早完成时间通过求各个结点的最早完成时间,来求来求关键路径关键路径.为此先给出两个概念为此先给出两个概念:2.结点结点v的先驱元集的先驱元集:令令D=为有向图为有向图,vV,称集合称集合 为为v的先驱元集的先驱元集.3.结点结点v的后继元集的后继元集:令令D=为有向图为有向图,vV,称集合称集合 为为v的后继元集的后继元集.v8 v5 v4v1 v7 v214203461 v6 v323144 4.最早完成时间最早完成时间:自发点自发点(记作记作v1)开始沿最长路径开始沿最长路径(按权计算按权计算)到达到达vi,称为称为vi的最早完成时间的最早完成时间,记作记作TE(vi),i=1,2,n 显然显然TE(v1)=0,收点收点vn最早完成时间最早完成时间TE(vn)就是从就是从v1到到vn的最长路径的长的最长路径的长.5.最晚完成时间最晚完成时间:在保证收点在保证收点vn的最早完成时间不增加的条件下的最早完成时间不增加的条件下,自发点自发点(记记作作v1)最迟到达最迟到达vi的时间的时间,称为称为vi的最晚完成时间的最晚完成时间,记作记作TL(vi),i=1,2,n 显然显然TL(vn)=TE(vn),v1 vj vi wijTL(vj)TL(vi)v1 vj vi wjiTE(vj)TE(vi)6.缓冲时间缓冲时间:称称 TS(vi)=TL(vi)TE(vi)i=1,2,n为为vi的的缓冲时间缓冲时间.7.关键路径关键路径:就是各个结点的缓冲时间均为就是各个结点的缓冲时间均为0的路径的路径.可见在关键路径上可见在关键路径上,如果一个工序增加了时间如果一个工序增加了时间t,则整个工则整个工程就推迟了时间程就推迟了时间t.所以才称之为关键路径所以才称之为关键路径.例如例如,求右图的关键路径求右图的关键路径(1)求各个结点的最早完成时间求各个结点的最早完成时间:TE(v1)=0TE(v2)=max0+1=1(v1)TE(v3)=max0+2,1+0=2 (v1v2)TE(v4)=max0+3,2+2=4 (v1v3)TE(v5)=max1+3,4+4=8 (v2v4)TE(v6)=max2+4,8+1=9 (v3v5)TE(v7)=max1+4,2+4=6 (v2v3)TE(v8)=max9+1,6+6=12(v6v7)v8 v5 v4v1 v7 v214203461 v6 v323144(2)求各个结点的最晚完成时间求各个结点的最晚完成时间:TL(v8)=TE(v8)=12TL(v7)=min12-6=6(v8)TL(v6)=min 12-1=11 (v8)TL(v5)=min 11-1=10 (v6)TL(v4)=min 10-4=6 (v5)TL(v3)=min 6-2,11-4,6-4=2 (v4v6v7)TL(v2)=min 2-0,10-3,6-4=2 (v3v5v7)TL(v1)=min 2-1,2-2,6-3=0 (v2v3v4)(3)求各个结点的缓冲时间求各个结点的缓冲时间 TS(vi)=TL(vi)-TE(vi)i v1 v2 v3 v4 v5 v6 v7 v8TL(vi)0 1 2 6 10 11 6 12TE(vi)0 1 2 4 8 9 6 12 TS(vi)0 0 0 2 2 2 0 0 v8 v5 v4v1 v7 v214213461 v6 v323144关键路径为关键路径为:v1v3v7v8作业：作业：P175 (22)(23)