运筹学-第3版-课件-最短路和匹配

1、第三节第三节 最短路问题最短路问题 最短路问题是网络理论中应用最广的问题之一。许多优化问题可以使这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。 最短路问题的一般提法如下：设G=（V，E）为连通图，图中各边 为图中任意两点，求一条道路 ，使他是从 的所有道路中总权最小的道路。即： 最小.(,)( )ijijv vLlstvv到,stv v( ,)(,)ijijijijv vl lv v 有权表示 有些最短问题也可以使球网络中某指定点到其余所有结点的最短路，过求网络中任意两点间的最短路。下面我们介绍三种算法，可分别用于求解这几种最短路问题。 一、一、DijkstraDij

2、kstra算法算法 本算法由Dijkstra于1959年提出，可用于求解指定两点 间的最短路，或从指定点 到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。算法的基本思想基于以下原理：若序列 是从 的最短路，则序列 必为从 的最短路。svn-1到v11( ,)snv vvsnvv到11 ,snnv vvvsv,stv v 基本步骤：?),(),(, 0),()(,)(010的长度到其余各顶点的最短路求规定有是连通赋权简单图，vvvwGEvvvvwGEvvvvvGVGjijijijin次迭代即得结果经过且代替用对任意的其中取）置（nniuSSvLvuwuLvLuSGVvSGVvv

3、LvLniSGVvuSnjvLvLiiiiiiiijiiij), 2 , 1(,),(),()(),(min,)()()(min)(), 2 , 1( ,)()2(), 2 , 1()(, 0)(1111100 求出从a到z的最短路的长度是？acbedz5421018263 解：0次迭代（初始化） L(a)=0,L(b)=L(c)=L(d)=L(e)=L(z)= ,S0= ; 一次迭代：取u1=a,S1=a L(a)+w(a,b)=0+4=4L(b) L(a)+w(a,c)=0+2=2L(c) L(a)+w(a,d)=0+ = L(a)+w(a,e)=L(a)+w(a,z)=0+ = ; L(

4、b)=4,L(c)=2,L(d)=L(e)=L(z)= 二次迭代：取u2=c, S2=a,c L(c)+w(c,b)=2+1=3L(b) L(c)+w(c,d)=2+8=10L(d) L(c)+w(c,e)=2+10=12L(e) L(c)+w(c,z)=2+ = L(b)=3,L(d)=10,L(e)=12,L(z)= 三次迭代：取u3=b, S3=a,c,b L(b)+w(b,d)=3+5=8L(d) L(b)+w(b,e)=3+ = L(b)+w(b,z)=3+ = L(d)=8, L(e)=12, L(z)= 四次迭代：取u4=d, S4=a,c,b,d L(d)+w(d,e)=8+2

5、=10L(e) L(d)+w(d,z)=8+6=14L(z) L(e)=10, L(z)=14; 五次迭代：取u5=e, S5=a,c,b,d,e L(e)+w(e,z)=10+3=13L(z) L(z)=13 结束：u6=z, S6=a,c,b,d,e,z 从a到z 的最短路的长度为13,最短路经为a,c,b,d,e,z 同样可以利用Dijkstra算法计算有向网络中最短有向路的长度，基本步骤如下：)2(,min,33,min,)2(), 3 , 2(, 1, 0, 3 , 2,1) 1 (,),(; 0,),(, 2 , 1)(),(,1再转置中每一个顶点）对（）终止，否则转（若置使得中寻

6、找一个点在且置有有有向网络jkwSSSjTTkTTkPPSSkTnjjwSSnTPjiwDAijjiwDAijnDVAVDkjjjTjkj 求出点1到其余各顶点的最短有向路的长度？1543253284731 Dijkstra算法:9, 3, 8, 5,0:918 ,11min5 , 3,min5,3 ,2,4, 1, 3115 ,11min5 ,2,min835 ,10min3 ,2,min5 , 3,2,4, 1,21183 ,min5 ,4,min1073 ,min3 ,4,min53 , 5min2,4,min5 , 3 ,2,4, 1,45 , 1, 34, 1,3 , 152, 1,

7、0,5 ,4, 3 ,2,15432135525523345543342254321SSSSSwSSSTPkwSSSwSSSTPkwSSSwSSSwSSSTPkwSwSwSwSSTP显然且 课堂练习1：利用Dijkstra算法，算出图中，v1到v5的最短路的长度？V1V3V2V4V5432758101 选址问题：已知某地区的交通网络如图5-39所示，其中点代表居民区，边表示公路， 为小区间公路距离，问区中心医院建在哪个小区，可使距离医院最远的小区居民就诊时所走的路程最近?ijl解：实际是要求出图的中心，可以化为一系列求最短路问题。先求出 v1 到其他各顶点的最短路长dj,令D(v1)=maxd

8、1,d2,d7,表示若医院建在v1, 则离医院最远的小区距离为D(v1),再依次计算v2,v3,v7到其余各点的最短路，类似求出D(v2),D(v3),D(v7), D(vi)(i=1,2,7)中最小者即为所求，计算结果见表5-3。由于 D(v6)=48最小，所以医院健在v6，此时离医院最远的小区 v5距离为48。v1v2v3v4v5v6v7D(vi)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548v7603040336315063Floy

9、dFloyd算法算法 某些问题中，要求网络上任意两点间的最短路，如例15就是这样。这类问题可以用Dijkstra算法一次改变起点的办法计算，但比较繁琐。这里介绍的Floyd方法（1962）可直接求出网络中任意两点间的最短路。 为计算方便，令网络的权矩阵为 。 其中 算法基本步骤为：的距离到为jijiwjiwldDijnnij),(,)(其他，当,),(,),(,Ejijijiwjiwdij 首先介绍矩阵的两种运算：),min()(,)(,)()2(),min()(,)(,)(12211ijijijnmijnmijnmijljiljijiijnmijnljklmijbaddBADbBaAbaba

10、baccBACbBaA其中规定：已知矩阵其中：规定）已知矩阵（。的所有路中长度最短者到是从结点最短者，而条边的路中长度经过到表示从结点由定义知，其中和然后算出矩阵没有边相连，则到如果结点若是有向图，则，的边权矩阵即：是设阶加权简单图已知jiskjidsDDDSdDDDdDDDdDDDSDDDdjijiwdjiwdGdDGnijkijnnijnnnnijnnnnijnnijnijijijnnij213232232)()(,)(,)(,),(),()(, 求图中任意两点间的最短有向路的长度？V1V4V5V3V2V6122173136631271312DDG为：的边权矩阵解：图423623482DD

11、D534623DDD634DDD没有有向路。到表示从；的最短有向路的长度为到表示从；的最短有向路的长度为到表示从5445533561166266552266631241235123456)()()(),()(vvsvvsvvssDDDSdDdDnnijnnijnnij课堂练习2：利用Floyd算法，算出图中任意两点之间的最短有向路的长度?1452365356423721 最大匹配问题： 考虑工作分配问题。有n个工人，m件工作，每个工人能力不同，各能胜任其中某几项工作。假设每件工作只需要一人做，每人只做一件工作，怎样分配才能尽量的工作有人做，更多的人有工作？ 这个问题可以用图的语言描述，如图5-

12、47。其中x1,x2,xn表示工人,y1,y2,ym表示工作，边（xi,yj)表示第i个人能胜任第j项工作，这样就得到了一个二部图G，用点集X表示x1,x2,xn，点集Y表示y1,y2,ym ,二部图G=(X,Y,E)。上述的工作分配问题就是要在图G中找一个边集E的子集，使得集中任何两条边没有公共端点，最好的方案就是要使此边集的边数尽可能多，这就是匹配问题。 定义定义2323 二部图 G=(X,Y,E) ，M是边集E的子集，若M中的任意两条边都没有公共端点，则称M为图G的一个匹配（也称对集）。 M中任意一条边的端点v称为（关于M的）饱和点，G中其他定点称为非饱和点。 若不存在另一条匹配 ，则称

13、M为最大匹配。 设M是G的一个匹配，P是G的一条道路，若P中的边是M与E(G)-M中的边交替出现的，则称P为M交错路；若起点和终点都是M非饱和点，则称P为M可扩路。 如何寻找二部图中的最大匹配问题？最早是由匈牙利数学家Egervary给出的,称为匈牙利算法： 基本思想：寻找非饱和点-寻找可扩路-作对称差1MM1使得 M）转（置中有一边饱和点，故是由于转置可扩路的到求一条从）；否则作：饱和点转（为若择一点则停止；否则，任意选）若（置非饱和点中寻找一个）在（）；否则转（中的每一个顶点，结束饱和）若（中的一个初始匹配）任意取（基本步骤：4,)6()2(),(,6)5(;)(,)(4;,3321yBBuSSyuMMyPEMMPMyxMyBSNyBSNBxSxMXXMMG