3第三章最短路问题

第三章最短路问题让我们先把最短路问题的提法明确一下§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并且长度最小的(无向)路找出来．上面两个问题都可以称为最短路问题．很容易看出，这两个问题都有着大量的生产实际背景.事实上，大至海、陆、空各种运输，小至一个人每天上班，都会遇到最短路问题.正因为它用处大，所以近二、三十年来国内外对这个问题进行了不少研究，也找到了许多比较好的计算方法.有趣的是，有些问题，从表面上看与最短路问题没有什么关系，却可以归结为最短路问题.下面就来举两个这样的例子：例1渡河问题：一个人带了一只狼、一只羊和一棵白菜想要过河,河上有一只独木船,每次除了人以外,只能带一样东西.另外,如果人不在旁时,狼就要吃羊,羊就要吃白菜.问应该怎样安排渡河,才能做到把所有东西都带过河去,而且在河上来回的次数又最少.当然，这个问题不用图论也能解决．大家一眼就能看出，第一次应该带着羊过河，让狼和白菜留下,以下怎么渡法呢？下面就来讲一下怎样把这个问题转化成最短路问题．我们用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表示人和羊在左岸，而狼和白菜在右岸；Ø表示左岸是空集，即人、狼、羊、白菜都已渡到右岸去了.检查一下就可以知道，这16种情况中有6种情况是不允许出现的.分别是：WSV,MW,MV,WS,SV,M.例如WSV表示狼、羊、白菜都在左岸而人在右岸，因为人不在旁边看着,狼就要吃羊，羊也要吃白菜；又如MV表示人和白菜在左岸，而狼和羊在右岸，当然也是不行的.因此，允许出现的情况只有10种.现在我们就来构造一个图G，它的顶点就是这10种情况，G中的边是按照下述原则来连的；如果情况甲经过一次渡河可以变成情况乙，那么就在情况甲与乙之间连一条边.WVWSVØMWSMWVWSVMSMWSV例如，MWSV经过一次渡河可以变成WV(人带着羊过河，左岸留下狼和白菜)，又例如MWV经过一次渡河可以变为W(人带着白菜过河，留下狼)，或变为V.当然反过来，W也可以变为MWV(人带着白菜从右岸返回左岸).作出了图G以后，渡河问题就归结为下述问题了：“在图G中找一条连接顶点MWSV与Ø，并且包含边数最少的路”.如果我们设G的每条边的长度都是1，那么也可以把渡河问题归结为：“找一条连接MWSV与Ø的最短路”.例2:某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升.现要将酒平分，求最少的操作次数.解设x1,x2,x3分别表示8,5,3升酒壶中的酒量.则1231238,8,5,3.xxxxxx容易算出(x1,x2,x3)的组合形式共24种.(0,5,3);(1,5,2);(1,4,3);(2,5,1);(2,4,2);(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)的一条最短路(求最短路的算法在有向图中仍适用).结果如下：(8,0,0)(3,5,0)(3,2,3)(6,2,0)(6,0,2)(1,5,2)(1,4,3)(4,4,0).每种组合用一个点表示，若点u能通过倒酒的方式变换为v,则u向v连有向边，并将各边赋权1，得一个有向赋权图.大家也许会认为，这两个例子本来就不很难，把它转化成图论问题，倒相当麻烦，有什么好处呢？其实这种做法还是很有好处的.因为在转化前，想解决这些问题，只能用凑的办法，或者最多是凭经验.而转化成图论问题以后，就可以用一种系统的方法解决了.最后，还要指出一下，求最短有向路和求最短无向路这两个问题是密切关联的.下面将看到，求最短有向路的计算方法也可以用来求最短无向路.在这一章中，我们假设遇到的图G都是简单图.这样假设是合理的，因为如果G有平行弧或平行边，例如有好几条从vi到vj的弧，那么很显然，可以把这些弧中最短的一条留下，其余的都去掉，然后在剩下的简单图上再来求从vs到vt的最短有向路.因为G是简单图，所以每一条弧ak被它的起点vi与终点vj唯一决定，因此，下面我们就用vi,vj或i,j来表示一条弧，用(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到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(1)代表从v1到v1的最短路的长度，当然不用计算就可以知道，它应该等于0.如果计算是在一张图上进行，那么我们可以在顶点v1旁边写一个数0，表示这是v1的标号并且已算出.每一轮计算可以分成下面几个步骤.步骤1找出所具有下述性质的弧i,j：起点vi是已标号点而终点vj是未标号点.如果这样的弧不存在，计算结束.步骤2对于步骤1中找到的每一条弧i,j，计算一个数：ki,j=b(i)+li,j.(如果这个ki,j在前面各轮计算中已经算过，就不必再算)也就是说：ki,j等于弧的起点的标号加上弧的长度.把算出的ki,j的值就写在弧i,j的旁边，并在数的外面加上一个方括号．然后找出使ki,j最小的弧c,d(如果有好几条弧都使ki,j达到最小，可任取一条)步骤3把弧c,d画成粗线，把顶点vd变为已标号点，令vd的标号b(d)就等于kc,d.这一轮计算结束.在一轮计算结束后，应该检查一下，是不是所有顶点都得到标号了，如果是的，那么整个计算就结束了；如果不是，即还有未标号的顶点，就转向下一轮计算(即再从步骤1开始计算).如果我们要求从vs到vt的最短路，只要vt得到标号，计算就结束了，从而可以省去一些计算.如果在计算结束时，还有一些点没有得到标号，那么可以肯定，从起点到这些点的有向路是不存在的.该计算方法的框式图如下：开始：令b(1)=0，v1为已标号点求所有起点已标号、终点未标号的弧的集合B，B是不是空集合？对于B中的每一条弧i,j，计算，ki,j=b(i)+li,j,求出使ki,j最小的弧c,d.将弧c,d加粗，令b(d)=kc,d,vd成为已标号点是否还有未标号的顶点计算结束是否是现在来讨论标号法好不好？要回答这个问题,首先应该明确一下什么叫“好”,什么叫“不好”．一般说来，主要的好坏标准是计算起来快不快不快(还有比的标准，例如容不容易拿上计算机计算；是否易于普及等等)，或者说，用这个方法计算时，需要进行的运算次数多不多.当然，运算次数越少越好.§3.3标号法好不好大家也许会说，运算次数多少不完全决定于采用什么方法，还和要解决的问题有关．同样用标号法，解一个只有10个顶点的问题可能只要进行几千次运算，而解一个100个顶点的问题，就可能要进行几百万次运算了，这又怎么比较呢？办法还是有的.那就是，设图G有n个顶点(为了简单起见，我们就不研究边数m的影响了),我们来估计一下，把标号法用到图G上去需要进行几次运算.当然，这样估计出来的结果不会是一个确定的数,而是象n2,3n3+4n2,2n等等这样的与n有关的数,即n的函数.然后再以这种函数为标准来比较方法的好坏.比如说，有两种方法，第一种要进行n3次加法，而第二种要进行n5次加法，当然第一种就比第二种好，因为在n较大时，n5比n3要大多了.上面讲的是怎样比较两种方法谁好谁坏.现在总共只讲了一个标号法，又怎么评论它的好坏呢？也有办法的.目前一般认为，如果一种方法所需要的运算次数能表示成n的多项式，例如n4,2n2+3n等等.这种方法就认为是好的，或者说是有效的.而如果一种方法的计算次数是某一个数的n次幂，例如2n,10n，即是n的指数函数，这种方法就认为是不好的，或者说是无效的.请看如下这张表：n5102030501001000方法A(运算次数n3)6251000800027000625000106109方法B(运算次数2n)321024≈106≈109≈1015≈1030≈10300上表中对一种需要进行n3次运算的方法A与另一种需要进行2n次运算的方法B进行了比较(关于2n的近似值,我们是以210=1024≈103来估算的,例如250=(210)5≈(103)5=1015).从上表可以看出，方法B的运算次数的增长速度是惊人的.也许有的人会认为，现在反正有大型计算机，计算次数多一些无所谓.其实不然.例如我们有一个每秒能计算一百万次的计算机，那么，在1000秒内可以进行1000×1000000=109次(即十亿次)运算,如果用方法A,则则可以解决一个1000个顶点的问题，而用方法B呢？却只能解决一个30个顶点的问题.如果想用方法B来解决一个100个顶点的问题，即使用的是每秒能计算一亿次的计算机，也需要1022秒，即要好几万亿年.从上面的简单比较久可以看出，为什么说计算次数是n的多项式的方法是有效的，而计算次数是n的指数函数的方法是无效的.另外，也可以看出，单靠提高计算机的速度还不够，还必须从数学上寻求有效的计算方法.现在再回过头来看看标号法好不好.回想一下标号法的各轮计算，可以看出，它只包含两种运算：加法与比较大小(比较大小也需要花费时间，所以也要考虑).加法用于计算k(i,j)，每计算一个k(i,j)进行一次加法，而且每一条弧最多只计算一次.因此,如果图中有m条弧，那么至多进行m次加法.对于一个有n个顶点的简单有向图来说，最多有n(n-1)条弧(假设从每一个顶点vi出发，都有n-1条弧指向其他的n-1个顶点)，因此，最多进行n(n-1)次加法，放宽一点，也可以说，至多进行n2次加法.另外，在每一轮计算中，在找使k(i,j)达到最小的弧c,d时，要用到比较大小的运算，一般说来，要从s个数中把最小的数找出来，要进行s-1次比较(例如有四个数a1,a2,a3,a4，那么可以先拿a1与a2比，然后拿这两个数中小的数