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

第三节 最短路问题 最短路问题是网络理论中应用最广的问题之一。许多优化问题可以使这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。 最短路问题的一般提法如下：设G=（V，E）为连通图，图中各边 为图中任意两点，求一条道路 ，使他是从 的所有道路中总权最小的道路。即： 最小. 有些最短问题也可以使球网络中某指定点到其余所有结点的最短路，过求网络中任意两点间的最短路。下面我们介绍三种算法，可分别用于求解这几种最短路问题。 一、Dijkstra算法 本算法由Dijkstra于1959年提出，可用于求解指定两点 间的最短路，或从指定点 到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。算法的基本思想基于以下原理：若序列 是从 的最短路，则序列 必为从 的最短路。 基本步骤： 求出从a到z的最短路的长度是？ 解：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(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=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算法计算有向网络中最短有向路的长度，基本步骤如下： 求出点1到其余各顶点的最短有向路的长度？ Dijkstra算法: 课堂练习1：利用Dijkstra算法，算出图中，v1到v5的最短路的长度？ 选址问题：已知某地区的交通网络如图5-39所示，其中点代表居民区，边表示公路， 为小区间公路距离，问区中心医院建在哪个小区，可使距离医院最远的小区居民就诊时所走的路程最近? 由于 D(v6)=48最小，所以医院健在v6，此时离医院最远的小区 v5距离为48。 Floyd算法 某些问题中，要求网络上任意两点间的最短路，如例15就是这样。这类问题可以用Dijkstra算法一次改变起点的办法计算，但比较繁琐。这里介绍的Floyd方法（1962）可直接求出网络中任意两点间的最短路。 为计算方便，令网络的权矩阵为 。 其中 算法基本步骤为： 首先介绍矩阵的两种运算： 求图中任意两点间的最短有向路的长度？ 课堂练习2：