《短路问题》PPT课件.ppt

第三章 最短路问题 让 我 们 先 把 最 短 路 问 题 的 提 法 明 确 一 下3.1 什么是最短路问题 1. 求有向图上的最短路问题：设G =(V,A)是一个有向图，它的每一条弧ai都有一个非负的长度l(ai).在G中指定了两个顶点vs与vt,要求把从vs到vt并且长度最小的有向路找出来 2. 求无向图上的最短(无向)路问题：设G =(V,E)是一个无向图，它的每一条弧e i都有一个非负的长度l(ei).在G中指定了两个顶点vs与vt,要求把连接vs与vt并且长度最小的(无向)路找出来 例2: 某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升.现要将酒平分，求最少的操作次数.解 设x1,x2,x3分别表示8,5,3升酒壶中的酒量.则1 2 3 1 2 38, 8, 5, 3.x x x x x x 容易算出(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，得一个有向赋权图. 这 一 节 介 绍 一 种 求 有 向 图 上 最 短 有 向 路 的 方法 ， 叫 做 标 号 法 。3.2 求最短有向路的标号法 所谓标号,我们是指与图的每一个顶点对应的一个数(或几个数)例如设G =(V,A)的顶点集合是V=v1,v2, ,vn，如果我们能使v1对应一个数b(1)，v2对应数b(2)，vn对应数b(n)，那么，这些数b(i)就称为vi的标号，当然，在不同的问题中，标号b(i)一般代表不同的意义. 现 在 来 讨 论 标 号 法 好 不 好 ？ 要 回 答 这 个 问 题 ,首先 应 该 明 确 一 下 什 么 叫 “ 好 ” ,什 么 叫 “ 不 好 ” 一般 说 来 ， 主 要 的 好 坏 标 准 是 计 算 起 来 快 不 快 不 快 (还有 比 的 标 准 ， 例 如 容 不 容 易 拿 上 计 算 机 计 算 ； 是 否易 于 普 及 等 等 )， 或 者 说 ， 用 这 个 方 法 计 算 时 ， 需 要进 行 的 运 算 次 数 多 不 多 .当 然 ， 运 算 次 数 越 少 越 好 .3.3 标号法好不好 大家也许会说，运算次数多少不完全决定于采用什么方法，还和要解决的问题有关同样用标号法，解一个只有10个顶点的问题可能只要进行几千次运算，而解一个100个顶点的问题，就可能要进行几百万次运算了，这又怎么比较呢？ 办法还是有的.那就是，设图G有n个顶点(为了简单起见，我们就不研究边数m的影响了),我们来估计一下，把标号法用到图G上去需要进行几次运算.当然，这样估计出来的结果不会是一个确定的数,而是象n2,3n3+4n2,2n等等这样的与n有关的数,即n的函数.然后再以这种函数为标准来比较方法的好坏.比如说，有两种方法，第一种要进行n 3次加法，而第二种要进行n5次加法，当然第一种就比第二种好，因为在n较大时，n5比n3要大多了. 上面讲的是怎样比较两种方法谁好谁坏.现在总共只讲了一个标号法，又怎么评论它的好坏呢？也有办法的.目前一般认为，如果一种方法所需要的运算次数能表示成n的多项式，例如n4,2n2+3n等等.这种方法就认为是好的，或者说是有效的.而如果一种方法的计算次数是某一个数的n次幂，例如2n,10n，即是n的指数函数，这种方法就认为是不好的，或者说是无效的.请看如下这张表：n 5 10 20 30 50 100 1000方法A(运算次数n 3) 625 1000 8000 27000 625000 106 109方法B(运算次数2n) 32 1024 106 109 1015 1030 10300 上表中对一种需要进行n3次运算的方法A与另一种需要进行2n次运算的方法B进行了比较(关于2n的近似值,我们是以210=1024103来估算的,例如250=(210)5(103)5=1015).从上表可以看出，方法B的运算次数的增长速度是惊人的.也许有的人会认为，现在反正有大型计算机，计算次数多一些无所谓.其实不然.例如我们有一个每秒能计算一百万次的计算机，那么，在1000秒内可以进行10001000000=109次(即十亿次)运算,如果用方法A,则则可以解决一个1000个顶点的问题，而用方法B呢？却只能解决一个30个顶点的问题.如果想用方法B来解决一个100个顶点的问题，即使用的是每秒能计算一亿次的计算机，也需要10 22秒，即要好几万亿年. 从上面的简单比较久可以看出，为什么说计算次数是n的多项式的方法是有效的，而计算次数是n的指数函数的方法是无效的.另外，也可以看出，单靠提高计算机的速度还不够，还必须从数学上寻求有效的计算方法. 现在再回过头来看看标号法好不好.回想一下标号法的各轮计算，可以看出，它只包含两种运算：加法与比较大小(比较大小也需要花费时间，所以也要考虑).加法用于计算k(i,j)，每计算一个k(i,j)进行一次加法，而且每一条弧最多只计算一次.因此,如果图中有m条弧，那么至多进行m次加法.对于一个有n个顶点的简单有向图来说，最多有n(n-1)条弧(假设从每一个顶点v i出发，都有n-1条弧指向其他的n-1个顶点)，因此，最多进行n(n-1)次加法，放宽一点，也可以说，至多进行n2次加法. 另外，在每一轮计算中，在找使k(i,j)达到最小的弧时，要用到比较大小的运算，一般说来，要从s个数中把最小的数找出来，要进行s-1次比较(例如有四个数a1,a2,a3,a4，那么可以先拿a1与a2比，然后拿这两个数中小的数与a3比，再拿小的数与a4比，比三次就能知道哪个数最小了).那么在每一轮的步骤1中，一般会选出几条弧呢？算得宽一些，至多n2条吧(事实上要少得多)，因此至多进行n2次比较，整个计算的轮数不会超过n，因此，总起来说，至多进行n3次比较大小的运算. 通过上面的估计，可以得出这样的结论：把标号法用在一个n个顶点的图上，至多进行n 2次加法和n3次比较大小.因此，可以说，标号法是一种好的、有效的计算方法. 问题：给定简单权图G = (V, E)，并设G 有n个顶点，求G中点u0到其它各点的最短路.Dijkstra算法 (Edmonds, 1965)(2) 若i = n-1，则停；否则令 = V Si , iS iSiS 对每个v ，令 l(v) = min l(v)，l(ui) + w(uiv)(1) 置 l(u0) = 0；对所有v V u0，令 l(v) = ； S0 = u0，i = 0. 3.4 求无向图上的最短路的方法 并用 ui+1记达到最小值的某点.置S i+1= Si u i+1，i = i+1（表示赋值语句，以后的算法中相同），转（2）.终止后，u0 到 v 的距离由 l(v) 的终值给出.)(min vliSv(3) 计算说 明 ： （1） 算法中w(uiv) 表示边 uiv 的权； （2） 若只想确定u0到某顶点v0的距离， 则当某 uj 等于 v0 时即停；（ 3） 算 法 稍 加 改 进 可 同 时 得 出 u 0到 其 它 点 的 最 短 路 . 例3 求图 G 中 u0 到其它点的距离.u0 7 42 1 55 813G :解 u0 7 42 1 55 813 （a）初始标号 u0 7 42 1 55 813 2 4 7（b）用与u0关联的边的权2,4,7分别更新与u0相邻的三个点的标号;（c）取小圆点中标号最小者得 u1； u0 7 42 1 55 813 2 4 7 u1 （d）对与u1相邻的小圆点，用 l (u1) + w (u1v) = 2+1 = 3更新标号4； 2+5=7 更新两个；u0 7 42 1 55 813 2 7 3 7 7 u1 （e）取小圆点中标号 最小者得 u2. u0 7 42 1 55 813 2 7 3 7 7 u1 u 2 u4 u0 7 42 1 55 813 2 7 3 4 6（h）u1 u2 0 u3u5 u0 7 42 1 55 813 2 7 3 7 7 u1 u2 4 （f）u0 7 42 1 55 813 2 7 3 6 u1 u2 （g）u0 7 42 1 55 813 2 7 3 4 6 u1 u 2 u3 3.5 图的距离表 以下图为例：这个图有6个顶点，在图3.5.2的(a)到(f)中分别画了以为起点的计算结果. 从上面的六张图虽然可以查出任意一个顶点到另一个顶点的距离，但是这样毕竟不太方便.比较方便的办法是把这些距离集中写在一张象如下的表上在这张表上，横着排的一行数字叫做“行”，竖着排的一列数字叫做“列”.在表中的第1行上，写的是从v1到各个顶点的距离，同样第2行是v2到各顶点的距离，.而第1列则是从各个顶点到v1的距离，其余各列也一样. )1()1()1()1( )1()1()1( kkjkikkijkij kkjkikkij dddr dddk若若 kpippippip prprpr k )(3)(2)( , 21jrqrqr pjqpjqpjp m )(2)(1)( , 11 v1 v2v3v4 v593 2 2 47 047 023 4202 7209 390)0(D 54321 54321 54321 54321 54321)0(R 047 02123 4202 712209 390)1(D 54321 54311 54321 51321 54321)1(R 0194716 1902123 420211 712209 1631190)2(D 52322 24311 54322 51321 24221)2(R 064615 60243 420211 64209 1531190)3(D 53333 34331 54322 33321 34221)3(R 06469 60243 42025 64207 93570)4(D 53334 34331 54324 33324 44441)4(R v6 v1 v2 v3v4v559 16 16171718 2241 302241 30 233123