《第三章最短路问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《第三章最短路问题ppt课件.ppt（53页珍藏版）》请在三一办公上搜索。
1、第三章 最短路问题,让我们先把最短路问题的提法明确一下,3.1 什么是最短路问题,1. 求有向图上的最短路问题：设G=(V,A)是一个有向图，它的每一条弧ai都有一个非负的长度l(ai).在G中指定了两个顶点vs与vt,要求把从vs到vt并且长度最小的有向路找出来,2. 求无向图上的最短(无向)路问题：设G=(V,E)是一个无向图，它的每一条弧ei都有一个非负的长度l(ei).在G中指定了两个顶点vs与vt,要求把连接vs与vt并且长度最小的(无向)路找出来,.,上面两个问题都可以称为最短路问题很容易看出，这两个问题都有着大量的生产实际背景.事实上，大至海、陆、空各种运输，小至一个人每天上班，
2、都会遇到最短路问题.正因为它用处大，所以近二、三十年来国内外对这个问题进行了不少研究，也找到了许多比较好的计算方法.,有趣的是，有些问题，从表面上看与最短路问题没有什么关系，却可以归结为最短路问题.下面就来举两个这样的例子：,例1 渡河问题：一个人带了一只狼、一只羊和一棵白菜想要过河,河上有一只独木船,每次除了人以外,只能带一样东西.另外,如果人不在旁时,狼就要吃羊,羊就要吃白菜.问应该怎样安排渡河,才能做到把所有东西都带过河去,而且在河上来回的次数又最少.,.,当然，这个问题不用图论也能解决大家一眼就能看出，第一次应该带着羊过河，让狼和白菜留下,以下怎么渡法呢？,下面就来讲一下怎样把这个问题
3、转化成最短路问题,我们用M代表人，W代表狼，S代表羊，V代表白菜.开始时，设人和其他三样东西都在河的左岸，这种情况，我们用MWSV来表示.又例如人带了羊渡到河的右岸去了，这时左岸留下了狼和白菜，这种情况就用WV来表示.例如MWS表示人(M)狼(W)羊(S)在左岸而白菜(V)在右岸这种情况.那么总共可能有几种允许的情况呢,.,如果不管狼是否吃羊、羊是否吃白菜，那么总共有16中情况，它们分别是：,MWSV, MWS, MWV, MSV, WSV, MW, MS, MV , WS, WV, SV, M, W, S, V, (空集),例如MS表示人和羊在左岸，而狼和白菜在右岸；表示左岸是空集，即人、狼
4、、羊、白菜都已渡到右岸去了.检查一下就可以知道，这16种情况中有6种情况是不允许出现的.分别是：WSV, MW, MV, WS, SV, M.例如WSV表示狼、羊、白菜都在左岸而人在右岸，因为人不在旁边看着,狼就要吃羊，羊也要吃白菜；又如MV表示人和白菜在左岸，而狼和羊在右岸，当然也是不行的.因此，允许出现的情况只有10种.,.,现在我们就来构造一个图G，它的顶点就是这10种情况，G中的边是按照下述原则来连的；如果情况甲经过一次渡河可以变成情况乙，那么就在情况甲与乙之间连一条边.,.,例如，MWSV经过一次渡河可以变成WV(人带着羊过河，左岸留下狼和白菜)，又例如MWV经过一次渡河可以变为W(
5、人带着白菜过河，留下狼)，或变为V.当然反过来，W也可以变为MWV(人带着白菜从右岸返回左岸).,作出了图G以后，渡河问题就归结为下述问题了：“在图G中找一条连接顶点MWSV与，并且包含边数最少的路”.如果我们设G的每条边的长度都是1，那么也可以把渡河问题归结为：“找一条连接MWSV与的最短路”.,.,例2: 某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升.现要将酒平分，求最少的操作次数.,解 设x1,x2,x3分别表示8,5,3升酒壶中的酒量.则,容易算出(x1,x2,x3) 的组合形式共24种.,(0,5,3);(1,5,2);(1,4,3);(2,5,1);(2,4,2)
6、;(2,3,3); (3,5,0);(3,4,1);(3,3,2);(3,2,3);(4,4,0);(4,3,1);(4,2,2);(4,1,3);(5,3,0);(5,2,1);(5,1,2);(5,0,3);(6,2,0);(6,1,1);(6,0,2);(7,1,0);(7,0,1);(8,0,0);,.,于是问题转化为在该图中求 (8,0,0)到(4,4,0)的一条最短路(求最短路的算法在有向图中仍适用).结果如下：,每种组合用一个点表示，若点u能通过倒酒的方式变换为v,则 u向v 连有向边，并将各边赋权1，得一个有向赋权图.,.,大家也许会认为，这两个例子本来就不很难，把它转化成图论
7、问题，倒相当麻烦，有什么好处呢？其实这种做法还是很有好处的.因为在转化前，想解决这些问题，只能用凑的办法，或者最多是凭经验.而转化成图论问题以后，就可以用一种系统的方法解决了.,最后，还要指出一下，求最短有向路和求最短无向路这两个问题是密切关联的.下面将看到，求最短有向路的计算方法也可以用来求最短无向路.,.,在这一章中，我们假设遇到的图G都是简单图.这样假设是合理的，因为如果G有平行弧或平行边，例如有好几条从vi到vj的弧，那么很显然，可以把这些弧中最短的一条留下，其余的都去掉，然后在剩下的简单图上再来求从vs到vt的最短有向路.因为G是简单图，所以每一条弧ak被它的起点vi与终点vj唯一决
8、定，因此，下面我们就用或来表示一条弧，用(vi,vj)或(i,j)来表示边，而用l(i,j)来表示弧或边的长度.,.,这一节介绍一种求有向图上最短有向路的方法，叫做标号法。,3.2 求最短有向路的标号法,所谓标号,我们是指与图的每一个顶点对应的一个数(或几个数)例如设G=(V,A)的顶点集合是V=v1,v2, ,vn，如果我们能使v1对应一个数b(1)，v2对应数b(2)，vn对应数b(n)，那么，这些数b(i)就称为vi的标号，当然，在不同的问题中，标号b(i)一般代表不同的意义.,.,回到我们要解决的最短有向路问题上来.为确定起见，我们设vs=v1，vt=vn,也就是说我们要找的是从v1到
9、vn的最短有向路.下面介绍的方法可以把从v1到G的每一个顶点vj的最短有向路都求出来(或者指出不存在从v1到vj的有向路，即v1不可达vj),我们把整个计算分成若干“轮”来进行(一个“轮”就是一个大步)，每一轮中，将求出v1到某一个顶点vj的最短路以及这条最短路的长度b(j).我们把b(j)就叫做顶点vj的标号.再强调一下，顶点vj的标号代表的是从v1到vj的最短路的长度.另外，如果说“顶点vj已经有标号了”或“vj是已标号点”，就意味着从v1到vj的最短路以及这条最短路的长度都已经求出来了.,.,计算开始时，令b(1)=0，v1变为已标号点，其余顶点都是未标号点.这样做的意义很清楚，因为b(
10、1)代表从v1到v1的最短路的长度，当然不用计算就可以知道，它应该等于0.,如果计算是在一张图上进行，那么我们可以在顶点v1旁边写一个数0，表示这是v1的标号并且已算出.,每一轮计算可以分成下面几个步骤.,步骤1 找出所具有下述性质的弧：起点vi是已标号点而终点vj是未标号点.如果这样的弧不存在，计算结束.,步骤2 对于步骤1中找到的每一条弧，计算一个数：k=b(i)+l.,.,(如果这个k在前面各轮计算中已经算过，就不必再算)也就是说：k等于弧的起点的 标号加上弧的长度.把算出的k的值就写在弧的旁边，并在数的外面加上一个方括号然后找出使k最小的弧(如果有好几条弧都使k达到最小，可任取一条),
11、步骤3 把弧画成粗线，把顶点vd变为已标号点，令vd的标号b(d)就等于k.这一轮计算结束.,在一轮计算结束后，应该检查一下，是不是所有顶点都得到标号了，如果是的，那么整个计算就结束了；如果不是，即还有未标号的顶点，就转向下一轮计算(即再从步骤1开始计算).,.,如果我们要求从vs到vt的最短路，只要vt得到标号，计算就结束了，从而可以省去一些计算.,如果在计算结束时，还有一些点没有得到标号，那么可以肯定，从起点到这些点的有向路是不存在的.,该计算方法的框式图如下：,.,开始：令b(1)=0，v1为已标号点,求所有起点已标号、终点未标号的弧的集合B，B是不是空集合？,对于B中的每一条弧，计算，
12、k=b(i)+l,求出使k最小的弧.,将弧加粗，令b(d)=k,vd成为已标号点,是否还有未标号的顶点,计算结束,是,否,是,.,现在来讨论标号法好不好？要回答这个问题,首先应该明确一下什么叫“好”,什么叫“不好”一般说来，主要的好坏标准是计算起来快不快不快(还有比的标准，例如容不容易拿上计算机计算；是否易于普及等等)，或者说，用这个方法计算时，需要进行的运算次数多不多.当然，运算次数越少越好.,3.3 标号法好不好,.,大家也许会说，运算次数多少不完全决定于采用什么方法，还和要解决的问题有关同样用标号法，解一个只有10个顶点的问题可能只要进行几千次运算，而解一个100个顶点的问题，就可能要进
13、行几百万次运算了，这又怎么比较呢？,办法还是有的.那就是，设图G有n个顶点(为了简单起见，我们就不研究边数m的影响了),我们来估计一下，把标号法用到图G上去需要进行几次运算.当然，这样估计出来的结果不会是一个确定的数,而是象n2,3n3+4n2,2n等等这样的与n有关的数,即n的函数.然后再以这种函数为标准来比较方法的好坏.比如说，有两种方法，第一种要进行n3次加法，而第二种要进行n5次加法，当然第一种就比第二种好，因为在n较大时，n5比n3要大多了.,.,上面讲的是怎样比较两种方法谁好谁坏.现在总共只讲了一个标号法，又怎么评论它的好坏呢？也有办法的.目前一般认为，如果一种方法所需要的运算次数
14、能表示成n的多项式，例如n4,2n2+3n等等.这种方法就认为是好的，或者说是有效的.而如果一种方法的计算次数是某一个数的n次幂，例如2n,10n，即是n的指数函数，这种方法就认为是不好的，或者说是无效的.请看如下这张表：,.,上表中对一种需要进行n3次运算的方法A与另一种需要进行2n次运算的方法B进行了比较(关于2n的近似值,我们是以210=1024103来估算的,例如250=(210)5(103)5=1015).从上表可以看出，方法B的运算次数的增长速度是惊人的.也许有的人会认为，现在反正有大型计算机，计算次数多一些无所谓.其实不然.例如我们有一个每秒能计算一百万次的计算机，那么，在100
15、0秒内可以进行10001000000=109次(即十亿次)运算,如果用方法A,则则可以解决一个1000个顶点的问题，而用方法B呢？却只能解决一个30个顶点的问题.如果想用方法B来解决一个100个顶点的问题，即使用的是每秒能计算一亿次的计算机，也需要1022秒，即要好几万亿年.,.,从上面的简单比较久可以看出，为什么说计算次数是n的多项式的方法是有效的，而计算次数是n的指数函数的方法是无效的.另外，也可以看出，单靠提高计算机的速度还不够，还必须从数学上寻求有效的计算方法.,现在再回过头来看看标号法好不好.回想一下标号法的各轮计算，可以看出，它只包含两种运算：加法与比较大小(比较大小也需要花费时间
16、，所以也要考虑).加法用于计算k(i,j)，每计算一个k(i,j)进行一次加法，而且每一条弧最多只计算一次.因此,如果图中有m条弧，那么至多进行m次加法.对于一个有n个顶点的简单有向图来说，最多有n(n-1)条弧(假设从每一个顶点vi出发，都有n-1条弧指向其他的n-1个顶点)，因此，最多进行n(n-1)次加法，放宽一点，也可以说，至多进行n2次加法.,.,另外，在每一轮计算中，在找使k(i,j)达到最小的弧时，要用到比较大小的运算，一般说来，要从s个数中把最小的数找出来，要进行s-1次比较(例如有四个数a1,a2,a3,a4，那么可以先拿a1与a2比，然后拿这两个数中小的数与a3比，再拿小的
17、数与a4比，比三次就能知道哪个数最小了).那么在每一轮的步骤1中，一般会选出几条弧呢？算得宽一些，至多n2条吧(事实上要少得多)，因此至多进行n2次比较，整个计算的轮数不会超过n，因此，总起来说，至多进行n3次比较大小的运算.,通过上面的估计，可以得出这样的结论：把标号法用在一个n个顶点的图上，至多进行n2次加法和n3次比较大小.因此，可以说，标号法是一种好的、有效的计算方法.,.,问题：给定简单权图G = (V, E)，并设G 有n个顶点，求G中点u0到其它各点的最短路.,Dijkstra算法 (Edmonds, 1965),(2) 若i = n-1，则停；否则令 = V Si ,对每个v
18、，令 l(v) = min l(v)，l(ui) + w(uiv),(1) 置 l(u0) = 0；对所有vV u0，令 l(v) = ； S0 = u0，i = 0.,3.4 求无向图上的最短路的方法,.,并用 ui+1记达到最小值的某点.置S i+1= Siu i+1，i = i+1（表示赋值语句，以后的算法中相同），转（2）.,终止后，u0 到 v 的距离由 l(v) 的终值给出.,说明：,（1） 算法中w(uiv) 表示边 uiv 的权；,（2） 若只想确定u0到某顶点v0的距离， 则当某 uj 等于 v0 时即停；,（3） 算法稍加改进可同时得出u0到其它点的最短路.,.,例3 求图
19、 G 中 u0 到其它点的距离.,u0,7,4,2,1,5,5,8,1,3,G :,解,.,（b）用与u0关联的边的权2,4,7分别更新与u0相邻的三个点的标号;,（c）取小圆点中标号最小者得 u1；,.,（d）对与u1相邻的小圆点，用 l (u1) + w (u1v) = 2+1 = 3更新标号4； 2+5=7 更新两个；,（e）取小圆点中标号 最小者得 u2.,.,.,3.5 图的距离表,在生产实践中，往往需要求出一个图的任意两个顶点之间的最短路.例如，一个铁路局在编制他所属的各个车站之间的运输里程表时，就会遇到这类问题另外，对于不少图论中的极值问题，往往在计算前首先必须把图中任意两个顶点
20、之间的最短路及最短路的长度都求出来.,要把一个图的任意两个顶点之间的最短路都求出来,并不困难.例如,在有向图上,用前面讲的方法,计算一次就可以把从v1到所有顶点的有向路都求出来了,接着从v2出发，就是一开始令v2为已标号点，并且令v2的标号b(2)=0，又可以把从v2到其它各点的最短路求出来，这样连续算n次，就可以把从任意一个顶点到另一个顶点的最短路都求出来了.对于无向图也可以用相似的方法来解决,.,以下图为例：这个图有6个顶点，在图3.5.2的(a)到(f)中分别画了以为起点的计算结果.,.,v1,2,v3,v2,v4,v5,v6,10,3,0,3,6,7,10,2,15,8,(a)起点v1
21、,8,10,7,图3.5.2,.,v1,5,v3,v2,v4,v5,v6,11,4,5,4,8,0,12,6,(b)起点v2,6,11,8,图3.5.2,.,v1,24,v3,v2,v4,v5,v6,15,23,24,23,19,7,19,(c)起点v3,0,7,15,图3.5.2,.,v1,13,v3,v2,v4,v5,v6,7,0,13,4,8,7,8,(d)起点v4,7,7,4,图3.5.2,.,v1,9,v3,v2,v4,v5,v6,3,8,9,8,4,3,4,(e)起点v5,3,3,0,图3.5.2,.,v1,17,v3,v2,v4,v5,v6,8,16,17,16,12,11,12
22、,(f)起点v6,11,0,8,图3.5.2,.,为方便起见，今后我们把从顶点vi到vj的最短路的长度叫做vi到vj的距离，记作d(vi,vj)或d(i,j),从上面的六张图虽然可以查出任意一个顶点到另一个顶点的距离，但是这样毕竟不太方便.比较方便的办法是把这些距离集中写在一张象如下的表上在这张表上，横着排的一行数字叫做“行”，竖着排的一列数字叫做“列”.在表中的第1行上，写的是从v1到各个顶点的距离，同样第2行是v2到各顶点的距离，.而第1列则是从各个顶点到v1的距离，其余各列也一样.,.,如上这样的表格叫做图G的距离表，从表上查顶点vi到顶点vj的距离要比从前面的六张图上查容易得多了,.,
23、1.2.3 每对顶点之间的最短路 求每对顶点之间最短路的算法是Floyd算法:1.算法的基本思路: 直接在图的带权邻接矩阵中用插入顶点的方法依次构造出p个矩阵D(1),D(2), ,D(p),使最后得到的矩阵D(p)成为图的距离矩阵,同时也求出插入点矩阵以便得到两点间的最短路径.2.算法原理:(1)求距离矩阵的方法:把带权邻接矩阵W作为距离矩阵的初值,即: D(0)=(dij(0)pp=W,.,10 D(1)=(dij(1) pp,其中dij(1)=mindij(0),di1(0)+d1j(0),dij(1)是从vi到vj的只允许以v1作为中间点的路径中最短路的长度.20 D(2)=(dij(
24、2) pp,其中dij(2)=mindij(1),di2(1)+d1j(1),dij(2),是从vi到vj的只允许以v1,v2作为中间点的路径中最短路的长度. P0 D(p)=(dij(p) pp,其中dij(p)=mindij(p-1),dip(p-1)+dpj(p-1),dij(p)是从vi到vj的只允许以v1,v2, ,vp作为中间点的路径中最短路的长度.即是从vi到vj中间可插入任何顶点的路径中最短路的长度,因此:D(P)即是距离矩阵.,.,(2)求路由矩阵的方法: 在建立距离矩阵的同时可建立路由矩阵R,R=(rij) pp,rij的含义是从vi到vj的最短路要经过点号为rij的点.
25、R(0)=(rij(0) pp,rij(0)=j每求得一个D(k)时,按下列方式产生相应的新的R(k): rij(k)= 即当vk被插入任何两点间的最短路径时,被记录在R(k)中,依次求D(p)时求得R(p),可由R(p)来查找任何点对之间最短路的路由.,.,(3)查找最短路路由的方法: 若rij(p)=p1,则点p1是点i到j点的最短路的中间点,然后用同样的方法再分头查找,若:向点i追溯得:向点j追溯得:则由点i到j的最短路的路由为:i,pk, ,p2,p1,q1,q2, ,qm,j,.,3.算法步骤:Floyd算法:求任意两点间的最短路:D(i,j):i到j的距离;R(i,j):i到j的插
26、入点.输入带权邻接矩阵W(i,j),(1)赋初值;对所有i,j: d(i,j)W(i,j),r(i,j)j,k1(2)更新d(i,j), r(i,j) :对所有i,j,若: d(i,k)+ d(k,j)d(i,j)则: d(i,j) d(i,k)+d(k,j), r(i,j) k (3)若k=p,停止;否则:k k+1,转(2).,.,下面给一个程序：Floyd-Warshall算法Input:非负元素的nn矩阵cijOutput: nn矩阵dij ，其中dij是在弧权为cij下，自i到j的最短路长度。Begin for all ij do dij:=cij; for i=1, ,n do d
27、ij:=; for j=1, ,n do for i=1, ,n ij do for k=1, ,n kj do dik:=mindik,dij+djkend,.,例3:求下面加权图的任意两点间的距离与路径.解:,.,插入v1得:矩阵中带下划线的元素为经迭代比较以后有变化的元素,即需要引入中间点v1,从而R(1)中相应的位置换为1.,.,插入v2得:插入v3得:,.,插入v4得:插入v5得:D(5)=D(4),R(5)=R(4) 从D(5)中得各顶点间的最短路,从R(5)中可追溯出最短路的路由.例如:从D(5)中得d51(5) =9,故从v5到v1的最短路为9,从R(5)中得r51(5)=4.
28、由v4向v5追溯: r54(5)=3, r53(5)=3;由v4向v1追溯: r41(5)=1.所以:从v5到v1的最短路径为:5341.,.,应用：可化为最短路问题的多阶段决策问题: 对于最优化问题中的多阶段决策问题,常可用动态规划来处理,它的特点是先将一个复杂的问题分解成相互联系的若干个阶段,每个阶段即为一个小问题,然后逐个处理.一旦每一个阶段的决策确定后,整个过程的决策也随之确定.但动态规划不存在一种标准的数学形式,可以说动态规划的使用是一种艺术,需要根据不同的实际问题列出相应的动态规划递推关系式,再求解递推关系,而不同的递推关系有不同的解法,没有一个统一的程序.对某些多阶段决策,.,问
29、题,要写出其动态规划递推关系难度很大,而图论中的最短路问题是一个多阶段决策问题,它可以用现成的Dijkstra算法求解.因此,对某些较复杂的多阶段决策问题,可以通过构造适当的图,将它转化成最短路问题,从而使问题变得清晰,直观.而一旦转化成功,剩下的就只是用标准的Dijkstra算法程序求解了. 要将一个多阶段决策问题化为最短路问题,关键在于对该问题构造出相应的图,使图的顶点,边,权分别对应于该问题的某些要素,从而图中某些顶点间的最短路就对应于该问题的解.有时对同一问题可以构造出不同的图. 下面通过一个实例来说明构造图的方法.,.,例4.(设备更新问题)企业使用一台设备,每年年初,企业领导就要确
30、定是购置新的,还是继续使用旧的.若购置新设备,就要支付一定的购置费用;若继续使用旧的,则需要支付一定的维修费用.现在要制定一个五年之内的设备更新计划,使得五年内总的支付费用最少. 已知该种设备在每年年初的价格为:(元)第一年 第二年 第三年 第四年 第五年 11 11 12 12 13使用不同时间设备所需维修费为:(元)使用年限:0-1 1-2 2-3 3-4 4-5维修费用: 5 6 8 11 18,.,解:构造如下所示带权有向图:(1)顶点集合V=v1,v2,v3,v4,v5,v6,其中:vi表示第i年(i=1,2,3,4,5)初购置新设备的决策,v6表示第5年底(2)弧集合E=(vi,vj)|i=1,2,3,4,5;ij6,弧(vi,vj)表示第i年初购进一台设备一直使用到第j年初的决策,其权w(vi,vj)表示由这一决策在第i年初到第j年初的总费用.如:w(v1,v4)=11+5+6+8=30,.,(3)问题转化为求v1到v6的最短路问题,求得两条最短路为:v1v4 v6;v1 v3 v6.权为:53.,.,
