第三章最短路问题课件.ppt

1、第三章第三章 最短路问题最短路问题 让我们先把最短路问题的提法明确一下让我们先把最短路问题的提法明确一下3.1 什么是最短路问题什么是最短路问题 1.求有向图上的最短路问题：设求有向图上的最短路问题：设G=(V,A)是一是一个有向图，它的每一条弧个有向图，它的每一条弧ai都有一个非负的长度都有一个非负的长度l(ai).在在G中指定了两个顶点中指定了两个顶点vs与与vt,要求把从要求把从vs到到vt并且长度最小的有向路找出来并且长度最小的有向路找出来 2.求无向图上的最短求无向图上的最短(无向无向)路问题：设路问题：设G=(V,E)是一个无向图，它的每一条弧是一个无向图，它的每一条弧ei都有一个

2、都有一个非负的长度非负的长度l(ei).在在G中指定了两个顶点中指定了两个顶点vs与与vt,要要求把连接求把连接vs与与vt并且长度最小的并且长度最小的(无向无向)路找出来路找出来 例例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);

3、(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)(

4、6,0,2)(1,5,2)(1,4,3)(4,4,0).每种组合用一个点表示，若点每种组合用一个点表示，若点u能通过倒酒的方式变能通过倒酒的方式变换为换为v,则则 u向向v 连有向边，并将各边赋权连有向边，并将各边赋权1，得一个有向，得一个有向赋权图赋权图.这一节介绍一种求有向图上最短有向路的方这一节介绍一种求有向图上最短有向路的方法，叫做法，叫做标号法。标号法。3.2 求最短有向路的标号法求最短有向路的标号法 所谓标号所谓标号,我们是指与图的每一个顶点对应的一个我们是指与图的每一个顶点对应的一个数数(或几个数或几个数)例如设例如设G=(V,A)的顶点集合是的顶点集合是V=v1,v2,vn，如

5、果我们能使，如果我们能使v1对应一个数对应一个数b(1)，v2对应数对应数b(2)，vn对应数对应数b(n)，那么，这些数，那么，这些数b(i)就称为就称为vi的标的标号，当然，在不同的问题中，标号号，当然，在不同的问题中，标号b(i)一般代表不同的一般代表不同的意义意义.现在来讨论标号法好不好？要回答这个问题现在来讨论标号法好不好？要回答这个问题,首首先应该明确一下什么叫先应该明确一下什么叫“好好”,什么叫什么叫“不好不好”一一般说来，主要的好坏标准是计算起来快不快不快般说来，主要的好坏标准是计算起来快不快不快(还还有比的标准，例如容不容易拿上计算机计算；是否有比的标准，例如容不容易拿上计算

6、机计算；是否易于普及等等易于普及等等)，或者说，用这个方法计算时，需要，或者说，用这个方法计算时，需要进行的运算次数多不多进行的运算次数多不多.当然，运算次数越少越好当然，运算次数越少越好.3.3 标号法好不好标号法好不好 大家也许会说，运算次数多少不完全决定于采大家也许会说，运算次数多少不完全决定于采用什么方法，还和要解决的问题有关同样用标号用什么方法，还和要解决的问题有关同样用标号法，解一个只有法，解一个只有10个顶点的问题可能只要进行几千个顶点的问题可能只要进行几千次运算，而解一个次运算，而解一个100个顶点的问题，就可能要进个顶点的问题，就可能要进行几百万次运算了，这又怎么比较呢？行几

7、百万次运算了，这又怎么比较呢？办法还是有的办法还是有的.那就是，设图那就是，设图G有有n个顶点个顶点(为了为了简单起见，我们就不研究边数简单起见，我们就不研究边数m的影响了的影响了),我们来我们来估计一下，把标号法用到图估计一下，把标号法用到图G上去需要进行几次运上去需要进行几次运算算.当然，这样估计出来的结果不会是一个确定的当然，这样估计出来的结果不会是一个确定的数数,而是象而是象n2,3n3+4n2,2n等等这样的与等等这样的与n有关的数有关的数,即即n的函数的函数.然后再以这种函数为标准来比较方法的好然后再以这种函数为标准来比较方法的好坏坏.比如说，有两种方法，第一种要进行比如说，有两种

8、方法，第一种要进行n3次加法次加法，而第二种要进行，而第二种要进行n5次加法，当然第一种就比第二次加法，当然第一种就比第二种好，因为在种好，因为在n较大时，较大时，n5比比n3要大多了要大多了.上面讲的是怎样比较两种方法谁好谁坏上面讲的是怎样比较两种方法谁好谁坏.现在总共只现在总共只讲了一个标号法，又怎么评论它的好坏呢？也有办法讲了一个标号法，又怎么评论它的好坏呢？也有办法的的.目前一般认为，如果一种方法所需要的运算次数能目前一般认为，如果一种方法所需要的运算次数能表示成表示成n的多项式，例如的多项式，例如n4,2n2+3n等等等等.这种方法就认这种方法就认为是好的，或者说是有效的为是好的，或

9、者说是有效的.而如果一种方法的计算次而如果一种方法的计算次数是某一个数的数是某一个数的n次幂，例如次幂，例如2n,10n，即是，即是n的指数函数的指数函数，这种方法就认为是不好的，或者说是无效的，这种方法就认为是不好的，或者说是无效的.请看如请看如下这张表：下这张表：n5102030501001000方法A(运算次数n3)6251000800027000 625000106109方法B(运算次数2n)3210241061091015103010300上表中对一种需要进行上表中对一种需要进行n3次运算的方法次运算的方法A与另一种需要进与另一种需要进行行2n次运算的方法次运算的方法B进行了比较进行

10、了比较(关于关于2n的近似值的近似值,我们是以我们是以210=1024103来估算的来估算的,例如例如250=(210)5(103)5=1015).从上表从上表可以看出，方法可以看出，方法B的运算次数的增长速度是惊人的的运算次数的增长速度是惊人的.也许有也许有的人会认为，现在反正有大型计算机，计算次数多一些无的人会认为，现在反正有大型计算机，计算次数多一些无所谓所谓.其实不然其实不然.例如我们有一个每秒能计算一百万次的计例如我们有一个每秒能计算一百万次的计算机，那么，在算机，那么，在1000秒内可以进行秒内可以进行10001000000=109次次(即十亿次即十亿次)运算运算,如果用方法如果用

11、方法A,则则可以解决一个则则可以解决一个1000个顶个顶点的问题，而用方法点的问题，而用方法B呢？却只能解决一个呢？却只能解决一个30个顶点的问个顶点的问题题.如果想用方法如果想用方法B来解决一个来解决一个100个顶点的问题，即使用个顶点的问题，即使用的是每秒能计算一亿次的计算机，也需要的是每秒能计算一亿次的计算机，也需要1022秒，即要好秒，即要好几万亿年几万亿年.从上面的简单比较久可以看出，为什么说计算从上面的简单比较久可以看出，为什么说计算次数是次数是n的多项式的方法是有效的，而计算次数是的多项式的方法是有效的，而计算次数是n的指数函数的方法是无效的的指数函数的方法是无效的.另外，也可以

12、看出，另外，也可以看出，单靠提高计算机的速度还不够，还必须从数学上寻单靠提高计算机的速度还不够，还必须从数学上寻求有效的计算方法求有效的计算方法.现在再回过头来看看标号法好不好现在再回过头来看看标号法好不好.回想一下标回想一下标号法的各轮计算，可以看出，它只包含两种运算：号法的各轮计算，可以看出，它只包含两种运算：加法与比较大小加法与比较大小(比较大小也需要花费时间，所以比较大小也需要花费时间，所以也要考虑也要考虑).加法用于计算加法用于计算k(i,j)，每计算一个，每计算一个k(i,j)进进行一次加法，而且每一条弧最多只计算一次行一次加法，而且每一条弧最多只计算一次.因此因此,如果图中有如果

13、图中有m条弧，那么至多进行条弧，那么至多进行m次加法次加法.对于一对于一个有个有n个顶点的简单有向图来说，最多有个顶点的简单有向图来说，最多有n(n-1)条条弧弧(假设从每一个顶点假设从每一个顶点vi出发，都有出发，都有n-1条弧指向其条弧指向其他的他的n-1个顶点个顶点)，因此，最多进行，因此，最多进行n(n-1)次加法，次加法，放宽一点，也可以说，至多进行放宽一点，也可以说，至多进行n2次加法次加法.另外，在每一轮计算中，在找使另外，在每一轮计算中，在找使k(i,j)达到最小达到最小的弧的弧时，要用到比较大小的运算，一般说来时，要用到比较大小的运算，一般说来，要从，要从s个数中把最小的数找

14、出来，要进行个数中把最小的数找出来，要进行s-1次比次比较较(例如有四个数例如有四个数a1,a2,a3,a4，那么可以先拿，那么可以先拿a1与与a2比比，然后拿这两个数中小的数与，然后拿这两个数中小的数与a3比，再拿小的数与比，再拿小的数与a4比，比三次就能知道哪个数最小了比，比三次就能知道哪个数最小了).那么在每一那么在每一轮的步骤轮的步骤1中，一般会选出几条弧呢？算得宽一些中，一般会选出几条弧呢？算得宽一些，至多，至多n2条吧条吧(事实上要少得多事实上要少得多)，因此至多进行，因此至多进行n2次比较，整个计算的轮数不会超过次比较，整个计算的轮数不会超过n，因此，总起，因此，总起来说，至多进

15、行来说，至多进行n3次比较大小的运算次比较大小的运算.通过上面的估计，可以得出这样的结论：把标通过上面的估计，可以得出这样的结论：把标号法用在一个号法用在一个n个顶点的图上，至多进行个顶点的图上，至多进行n2次加法次加法和和n3次比较大小次比较大小.因此，可以说，标号法是一种好因此，可以说，标号法是一种好的、有效的计算方法的、有效的计算方法.问题：问题：给定简单权图给定简单权图G=(V,E)，并设，并设G 有有n个顶个顶点，求点，求G中点中点u0到其它各点的最短路到其它各点的最短路.Dijkstra算法算法 (Edmonds,1965)(2)若若i=n-1，则停；否则令，则停；否则令 =V S

16、i,iSiSiS 对每个对每个v ，令，令 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)的终值给出的终值给出.)(minvliSv(3)计算计算说明：说明：（1）算法中算法中w(uiv)表示边表示边 u

17、iv 的权；的权；（2）若只想确定若只想确定u0到某顶点到某顶点v0的距离，的距离，则当某则当某 uj 等于等于 v0 时即停；时即停；（3 3）算法稍加改进可同时得出算法稍加改进可同时得出u u0 0到其它点的最短路到其它点的最短路.例例3 求图求图 G 中中 u0 到其它点的距离到其它点的距离.u0 742155813G:解解 u0 742155813 （a）初始标号）初始标号u0 742155813 2 4 7（b）用与）用与u0关联的边的关联的边的权权2,4,7分别更新与分别更新与u0相邻相邻的三个点的标号的三个点的标号;（c）取小圆点中）取小圆点中标号最小者得标号最小者得 u1；u0

18、 742155813 2 4 7u1（d）对与对与u1相邻的小圆点，相邻的小圆点，用用 l(u1)+w(u1v)=2+1=3更新标号更新标号4；2+5=7 更新两个更新两个；u0 742155813 2 7 37 7u1（e）取小圆点中标号）取小圆点中标号 最小者得最小者得 u2.u0 742155813 2 7 37 7u1 u2 u4 u0 742155813 2 7 34 6（h）u1 u2 0u3u5 u0 742155813 2 7 37 7u1 u2 4（f）u0 742155813 2 7 3 6u1 u2（g）u0 742155813 2 7 34 6u1 u2 u33.5 图

19、的距离表图的距离表 以下图为例：这个图有以下图为例：这个图有6个顶点，在图个顶点，在图3.5.2的的(a)到到(f)中分别画了以为起点的计算结中分别画了以为起点的计算结果果.从上面的六张图虽然可以查出任意一个顶点到另一从上面的六张图虽然可以查出任意一个顶点到另一个顶点的距离，但是这样毕竟不太方便个顶点的距离，但是这样毕竟不太方便.比较方便的办比较方便的办法是把这些距离集中写在一张象如下的表上在这张法是把这些距离集中写在一张象如下的表上在这张表上，横着排的一行数字叫做表上，横着排的一行数字叫做“行行”，竖着排的一列，竖着排的一列数字叫做数字叫做“列列”.在表中的第在表中的第1行上，写的是从行上，

20、写的是从v1到各个到各个顶点的距离，同样第顶点的距离，同样第2行是行是v2到各顶点的距离，到各顶点的距离，.而而第第1列则是从各个顶点到列则是从各个顶点到v1的距离，其余各列也一样的距离，其余各列也一样.)1()1()1()1()1()1()1(kkjkikkijkijkkjkikkijdddrdddk若若kpippippipprprprk)(3)(2)(,21jrqrqrpjqpjqpjpm)(2)(1)(,11v1v2v3v4v593224704702342027209390)0(D5432154321543215432154321)0(R047021234202712209390)1(D5432154311543215132154321)1(R019471619021234202117122091631190)2(D5232224311543225132124221)2(R06461560243420211642091531190)3(D5333334331543223332134221)3(R0646960243420256420793570)4(D5333434331543243332444441)4(Rv6v1v2v3v4v5591616171718224130224130233123