最短路径问题的几个算法.docx

《最短路径问题的几个算法.docx》由会员分享，可在线阅读，更多相关《最短路径问题的几个算法.docx（15页珍藏版）》请在三一办公上搜索。

1、最短路径问题的几个算法 最短路径问题) r+ g v% 5 p) W) J 最短路径问题是一个非常能联系实际的问题，某人想从城市A出发游览各 城市一遍，而所用费用最少。试编程序输出结果。 解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。 实际上我们知道，递归、深度搜索等算法一般用于求所有解问题，而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。 : V7 ) v g3 首先，对于

2、这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下： const dis:array1.5,1.5 of integer =( ( 0, 7, 3,10,15), 0 u; Y0 O i2 L/ i ( 7, 0, 5,13,12), ( 3, 5, 0, 5,10), 8 I- f E: D1 J (10,13, 5, 0,11), (15,12,10,11, 0); 以下是几种解法： 3 G3 c# u e- I7 y 一、 宽度优先搜索 % O9 O4 G3 W, L9 l3 Q9 O 宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它的算法

3、。 具体方法是： 2 c d6 Y) / t9 h3 c/ i 1、 从A点开始依次展开得到AB、AC、AD、AE四个新结点，当然每个新结点要记录下其距离； 2、 再次以AB展开得到ABC、ABD、ABE三个新结点，而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离； 5 n. d+ B5 7 A; v 3、 再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、BEC、ABEDAEDB、AEDC，每个结点也需记录下其距离； 4、 再把第

4、四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、AE 1 5 2 0 r: I V* h DBC、AEDCB，每个结点也需记录下其距离； 5、 到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。 由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。 ) p. ?+ X5 c: B* 5 u4 j7 O 二、 A算法 A算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点，而把该结点展开，直到找到目标

5、结点为止。 2 _0 Z. d; G* A( E+ & W9 V* 这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A算法实现起来并不难，只不过难在找准估价函数，大家可以自已找资料看看。 三、等代价搜索法 0 J3 J$ W( z% c/ m5 ?: l k) ? K 等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A算法的相似之处都是每次只展开某一个结点，不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A算法的一种简化版本。它的大体思路是： 1、 从A点开始依次展开得到AB、AC、AD、AE四个新结

6、点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离； 0 z G0 p3 V( K X 2、 把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC结点，得到ACB、ACD、ACE三个结点，并把结点AC标记为已展开； 3、 再从未展开的所有结点中找出距离最小的一个展开，即展开AB结点，得到ABC、ABD、ABE三个结点，并把结点AB标记为已展开； 4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB结点； 5、 每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况时，即得到了结果。 由上可见，A算法和等代价搜索法并没有象宽度优

7、先搜索一样展开所有结点，只是根据某一原则每次展开距离A点最近的那个结点，反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。 U8 9 Y5 5 b4 U 例2、题目基本同例1、但只要求求A到E点的最短路径。 3 8 u6 7 0 _# _ 题目一改，问题的关键变了，所要求的结果并不是要求每个点都要走一遍，而是不管走哪几个点，只要距离最短即可。再用宽度优先搜索已经没有什么意义了，那么等代价搜索能不能再用在这题上呢？ 答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。 ! i3 + n,

8、 w, m. _0 I+ d3 y, 8 b/ z 是不是搜索到一个结点是以E结束时就停止呢？显然不对。 那么是不是要把所有以E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。 ( q2 w3 L0 # d4 2 6 s2 M 实际上，应该是搜索到：当我们确定将要展开的某个结点的最后一个字母是E时，这个结点就是我们所要求的答案！ 9 ; x: j% |) V8 那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍求最短路径问题的第四种算法： ( Y0 H- h# 5 G 四、Warshall算法 该算法的中心思想是：任意两点i,j间的最短距离会等于从i点出发到达j点的以任一点

9、为中转点的所有可能的方案中，距离最短的一个。即： Dij=min(Dij,Dik+Dkj，)，1=k0，求生成树 T = ，H E，使生成树所有边权最小，此生成树称为最小生成树 基本回路 将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝将任一连枝加到生成树上后都会形成一条回路把这种回路称为基本回路，记为cf(e)。 基本回路是由 T 中的树枝和一条连枝构成的回路 基本割集 设无向图 G 的割集 S ，若 S 中仅包含有T中的一条树枝，则称此割集为基本割集，记为S(e)。 基本割集是集合中的元素只有一条是树枝，其他的为连枝 等长变换 设T=(V,H),为一棵生成树，e

10、 H, e E, e H,当且仅当ecf(e)，也就是说e S(e)，则T=Te, e也是一棵生成树。当w(e)=w(e)时，这棵生成树叫做等长变换。 等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树 根据以上定理得出2个结论：若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边由上面结论可以得到唯一性：若图 G 中的生成树T = 是唯一的一棵最小生成树，当且仅当任意一连枝e H, e E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集S(e)中的唯一最短边 由此在最小

11、生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最小生成树T0。对于T0中每一条树边e H，若 e 是基本割集S(e)中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。 对于每条连枝e H, e E，若它是基本回路cf(e)中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其消去 约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树T0中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边在基本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉通过这样约化后再求最小生成树，计算量会大

12、大下降 1.2 全部最小生成树 设T0是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他最小生成树 T，称T-T0得到的边集的长度为距离。 为了简单起见，设最小生成树T0的边集为 e1 , e2, e3 en-1，对于T0的任何边集Hk= e1 , e2, e3 ek-1，则每棵最小生成树 T 与T0的距离是一定的，或为1，或为2 ，或为 n -1这样我们就可以按所有的最小生成树与T0的距离来分类。 记Ti1,i2,ik= e1 , e2, e3 ek-1为所有的T0Hk即不含Hk的最小生成树的集合对于其它的最小生成树TTi1,i2,ik而言，Hk=T0T为换出边，Hk=TT0为入

13、边，T0T中的边叫不动边若 T 有 k 个换出边就说它与T0的距离为 k当 k=0 时为参考树本身。 当 k = 1 时，对任意的1in-1，有Ti1=T0ei1,p|pSi1(T0),w(p)=w(ei1),pei1。最小生成树Ti1是用基本割集Si1的边 p 换出T0的边ei1且边p 的权和边ei1的权相等。 当 k = 2时，Ti1,ij=Ti1eij,p|pSij(T0)Sij(Tij),w(p)=w(eij),peij。在换入一条边后得到的生成树中再换入一条边，即换入两条边后得到的一棵最小生成树Ti1,ij。 以此递推下去，可建立如下关系：Ti1,i2ik=Ti1,i2ikeik-1

14、,p|pSij(Ti1,i2k-1)S(T0),w(p)=w(eik),peik此递推关系表示在换入k 1条边后得到的生成树中再换入一条边后得到的一棵最小生成树用此递推关系，就可以求出全部的最小生成树。 2 算法 选取一棵最小生成树T0，求出T0 的全部基本回路对每一个基本回路去掉唯一最大边，约化所给的图然后对应于T0 的每条树边，求出基本割集若此树边也是基本割集中唯一最短边，则取其为固定边，并将此基本割集作上记号，求其他的最小生成树时，就不用考虑此割集了其余的基本割集，应用递推关系，对应于递推式求出所有的换入边对于距离为1的，每一个换入边对应着一棵最小生成树；对于距离为2 的每两个换入边也对

15、应着一棵最小生成树；换入 k 条边，就对应着距离为 k 的最小生成树以此类推就可以求出全部的 最小生成树 求无向图 G 的全部最小生成树的算法如下 求最小生成树T0 比较成熟的算法，在此就不做介绍 求约化图算法 Step1 令p=p1,p2,p3,pb为连枝集合，j=1； Step2 在T0 中加入连枝pj，形成一个基本回路，记为cfj； Step 3 若pj 是基本回路cfj中唯一最长边，则从图 G 中去掉pj； Step4 j =j +1,若 j 不大于 b，则返回Step2； Step5 输出经约化后的图 G。 求固定边算法 Step 1 令 E = e1 , e2, e3 en-1为最

16、小生成树T0的树枝集合，S =S1,S2,Sn-1，Si为树枝ei的基本割集，i=1; Step 2 从约化后的图 G 中求出树枝ei的基本割集Si； Step3 若ei 是基本割集 S 中的唯一最短边，则将ei 取为固定边，并对Si作记号； Step4 i 增加1, 若 i 不等于n, 则返回Step2 求换入边算法 Step1 设 H 为换入边的集合，F 为换出边的集合，初始 H、F 为空，i=1； Step 2 若ei的基本割集Si =P1,P2,Pd中有记号，则ei 为固定边，执行Step 8； Step3 若ei的基本割集Si 中无记号，则ei 放入 F 中； Step4 令 k=

17、1； Step 5 若eiPk，且权w(ei)=w(pk)，pk放入H中； Step6 k =k+ 1； Step7 若 k d 则返回Step5； Step 8 i = i +1，若 i 小于或等于 n 1, 则返回Step 2 求全部最小生成树算法 按距离从1到g 求全部最小生成树） 设 H =P1,P2,Pm为换入边的集合，F =e1,e2,eg为换出边的集合 Step 1 若 H 为空，则最小生成树是唯一，输出T0，算法结束 ( ) Step2 k =1, T11=T0 , 输出T0 , ； Step3 j =k； Step4 若ekjpj, 且权w(ekj）=w(pj)，则在Tkj中

18、用pj代替ekj，输出Tkj; Step 5 j = j +1，若 j小于或等于m，重复上面的Step 4； Step 6 k = k + 1，若 k 小于或等于 g，则返回Step 3； Step7 结束 3 应用举例 例 如图1 (a) 所示，无向图 G 是有权无向连通图，求全部最小生成树 设由图 1 (a) 得到一棵如图1( b) 所示的最小生成树称T0 基本回路是由树枝和一条连枝组成的回路，由“破圈法”的思想，若此连枝是基本回路中的唯一最长边，则将此边去掉后得到约化图无向图G的基本回路中的唯一最长边为：在基本回路-中有唯一最长边是，其权为7，将其去掉；在基本回路-中有唯一最长边是，其权

19、为3，将其去掉；在基本回路-中有唯一最长边是，其权为4，将其去掉；在基本回路-中有唯一最长边是，其权为 8，将其去掉去掉基本回路中的唯一最长的边后，形成如图1 (c) 所示的约化图 对无向图 G 进行约化后，最小生成树T0 中各边的基本割集为： ，为唯一最短边，取为固定边，将此割集作上记号；：， ；：，；：，为唯一最短边，取为固定边，将此割集作上记号；：， ，为唯一最短边，取为固定边，将此割集作上记号；：， ，为唯一最短边，取为固定边，将此割集作上记号 在T0 中，取为固定边的有 ， 这样其他的最小生成树只能在 ， 和 ， 这两个基本割集中选取了根据算法，得到换入边为 ， ，换出边为 ， 当

20、k = 1 时，换入一条边得到的最小生成树W( )=w，用边换得到最小生成树a，如图1 所示；w =w ，用换得到最小生成树b，如图1 所示； k =2 时，用换后，再用换得到的最小生成树c，如图1 所示 4 结论 本文在对连通图的特征进行分析的基础上，得出在某个基本回路 C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边，将此边从无向图 G 中去掉，对图进行约化；若在某个边 e的割集中有一条唯一最短边，则每棵生成树中都必须含这条边，则取为固定边利用“破圈法”的思想去掉基本回路中的唯一最长边，保留基本割集中唯一最短边，对连通图进行约化，在约化图的基础上求全部最小生成树，计算量会大量地下

21、降，算法的效率将大大地提高 二.Floyd算法 1. Floyd算法的基本思想： 可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到

22、j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。 2. Floyd算法的基本步骤： 定义nn的方阵序列D-1, D0 , Dn1, 初始化： D-1C D-1ij边的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。 迭代：设Dk-1已求出，如何得到Dk？ Dk-1ij表示从i到j的中间点不大于k-1的最短路径p：ij， 考虑将顶点k加入路径p得到顶点序列q：ikj， 若q不是路径，则当前的最短路径仍是

23、上一步结果：Dkij= Dk1ij； 否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。 因为q的两条子路径ik和kj皆是中间点不大于k1的最短路径，所以从i到j中间点不大于k的最短路径长度为： Dkijmin Dk-1ij, Dk-1ik +Dk-1kj Floyd算法实现： 可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序：我们可能随手就会写出这样的程序，但是仔细考虑的话，会发现是有问题的。 for(int i=0; in; i+) for(int j=0; jn; j+) for(int k=0; kn; k+) 问题出在我们太早的把i

24、-k-j的距离确定下来了，假设一旦找到了i-p-j最短的距离后，i到j就相当处理完了，以后不会在改变了，一旦以后有使i到j的更短的距离时也不能再去更新了，所以结果一定是不对的。所以应当象下面一样来写程序： for(int k=0; kn; k+) for(int i=0; in; i+) for(int j=0; j.-p-j，也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后，要找最短路径就轻而易举了。对于i到j而言找出p(ij)，令为p，就知道了路径i-.-p-j；再去找p(ip)，如果值为q，i到p的最短路径为i-.-q-p；再去找p(i

25、q)，如果值为r，i到q的最短路径为i-.-r-q；所以一再反复，到了某个p(it)的值为i时，就表示i到t的最短路径为i-t，就会的到答案了，i到j的最短行径为i-t-.-q-p-j。因为上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。 但是，如何动态的回填P矩阵的值呢？回想一下，当d(ij)d(ik)+d(kj)时，就要让i到j的最短路径改为走i-.-k-.-j这一条路，但是d(kj)的值是已知的，换句话说，就是k-.-j这条路是已知的，所以k-.-j这条路上j的上一个城市(即p(kj)也是已知的，当然，因为要改走i-.-k-.-j这一条路，j的上一个城市正好是p(kj)。所以一旦发现d(ij)d(ik)+d(kj)，就把p(kj)存入p(ij)。 此外，还有All-Pairs算法、Dijkstra算法等算法