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

最短路径问题) r+ g v% 5 p) W) J 最短路径问题是一个非常能联系实际的问题，某人想从城市A出发游览各 城市一遍，而所用费用最少。试编程序输出结果。/ c+ r2 x8 S7 j! N4 z解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。/ N% M0 K* & X2 A& U4 l. / f实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。 : V7 ) v g3 首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下：( N8 b. x+ V/ e3 Z% Y; yconst dis:array1.5,1.5 of integer =( ( 0, 7, 3,10,15), 0 u; Y0 O i2 L/ i ( 7, 0, 5,13,12),% U5 D# I& L/ F( ) y( j9 x6 o( 3, 5, 0, 5,10), 8 I- f E: D1 J(10,13, 5, 0,11),$ W P1 8 T, + p x. S- Z! a(15,12,10,11, 0);# p! L4 |+ b; c) V以下是几种解法： 3 G3 c# u e- I7 y一、 宽度优先搜索 % O9 O4 G3 W, L9 l3 Q9 O宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它的算法。$ Q s5 d, b$ N/ c3 V, ?+ Z具体方法是： 2 c d6 Y) / t9 h3 c/ i1、 从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；1 ?1 g, G. | n# D* O) 8 A2、 再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离； 5 n. d+ B5 7 A; v3、 再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、BEC、ABEDAEDB、AEDC，每个结点也需记录下其距离；$ u) % i; V8 m0 0 m6 p4、 再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、AE 1 5 2 0 r: I V* hDBC、AEDCB，每个结点也需记录下其距离； ; v2 Y/ T. ( 1 r9 Y5、 到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。2 w3 R4 O Q. c+ q; R+ R7 q3 由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。 ) p. ?+ X5 c: B* 5 u4 j7 O二、 A算法# K4 e4 |- I$ x+ O1 y# 8 A算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。 2 _0 Z. d; G* A( E+ & W9 V* 这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A算法实现起来并不难，只不过难在找准估价函数，大家可以自已找资料看看。/ D1 T7 1 u+ E8 b三、等代价搜索法 0 J3 J$ W( z% c/ m5 ?: l k) ? K等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A算法的一种简化版本。它的大体思路是：: E! k O p1、 从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离（括号中的数字）； 0 z G0 p3 V( K X 2、 把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开；) B+ 0 W1 S% |3、 再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开；5 ! N d% z& E2 R R4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点；7 z E4 i1 f U2 v c5 i N$ N5、 每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。 G4 y0 _7 ?; l & o! F由上可见，A算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。 U8 9 Y5 5 b4 U例2、题目基本同例1、但只要求求A到E点的最短路径（并不要求每个城市都要走一遍）。 3 8 u6 7 0 _# _题目一改，问题的关键变了，所要求的结果并不是要求每个点都要走一遍，而是不管走哪几个点，只要距离最短即可。再用宽度优先搜索已经没有什么意义了，那么等代价搜索能不能再用在这题上呢？5 x% L: S2 B: q) 答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。 ! i3 + n, w, m. _0 I+ d3 y, 8 b/ z是不是搜索到一个结点是以E结束时就停止呢？显然不对。/ v1 Q: N# w7 F6 A z/ 0 v那么是不是要把所有以E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。 ( q2 w3 L0 # d4 2 6 s2 M实际上，应该是搜索到：当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是E时，这个结点就是我们所要求的答案！ 9 ; x: j% |) V8 那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍求最短路径问题的第四种算法： ( Y0 H- h# 5 G四、Warshall算法6 y+ H! ? S- 8 _4 g( P/ E该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即：- g6 v1 e. z! Q& o! / Dij=min(Dij,Dik+Dkj，)，1=k0，求生成树 T = （V,H），H E，使生成树所有边权最小，此生成树称为最小生成树（1） 基本回路将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝将任一连枝加到生成树上后都会形成一条回路把这种回路称为基本回路，记为。基本回路是由 T 中的树枝和一条连枝构成的回路（2） 基本割集设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T中的一条树枝，则称此割集为基本割集，记为。基本割集是集合中的元素只有一条是树枝，其他的为连枝（3） 等长变换 设T=(V,H),为一棵生成树，e H, E, H,当且仅当，也就是说e ，则=Te, 也是一棵生成树。当=时，这棵生成树叫做等长变换。等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树根据以上定理得出2个结论：若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边由上面结论可以得到唯一性：若图 G 中的生成树T = （V,H）是唯一的一棵最小生成树，当且仅当任意一连枝e H, E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集中的唯一最短边由此在最小生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最小生成树。对于中每一条树边e H，若 e 是基本割集中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。对于每条连枝e H, E，若它是基本回路中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其消去约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此边，就取为固定边在基本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉通过这样约化后再求最小生成树，计算量会大大下降1.2 全部最小生成树设是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他最小生成树 T，称T-得到的边集的长度为距离（这里的长度是指集合中元素的个数）。为了简单起见，设最小生成树的边集为 , , ，对于的任何边集= , , （），则每棵最小生成树 T 与的距离是一定的，或为1，或为2 ，或为 n -1这样我们就可以按所有的最小生成树与的距离来分类。记= , , 为所有的即不含的最小生成树的集合（可能为空）对于其它的最小生成树T而言，=T为换出边，=T为入边，中的边叫不动边若 T 有 k 个换出边就说它与的距离为 k当 k=0 时为参考树本身。当 k = 1 时，对任意的，有。最小生成树是用基本割集的边 p 换出的边且边p 的权和边的权相等。当 k = 2时，。在换入一条边后得到的生成树中再换入一条边，即换入两条边后得到的一棵最小生成树。以此递推下去，可建立如下关系：此递推关系表示在换入k 1条边后得到的生成树中再换入一条边后得到的一棵最小生成树用此递推关系，就可以求出全部的最小生成树。2 算法 选取一棵最小生成树，求出 的全部基本回路对每一个基本回路去掉唯一最大边，约化所给的图然后对应于 的每条树边，求出基本割集若此树边也是基本割集中唯一最短边，则取其为固定边，并将此基本割集作上记号，求其他的最小生成树时，就不用考虑此割集了其余的基本割集，应用递推关系，对应于递推式求出所有的换入边对于距离为1的，每一个换入边对应着一棵最小生成树；对于距离为2 的每两个换入边也对应着一棵最小生成树；换入 k 条边，就对应着距离为 k 的最小生成树以此类推就可以求出全部的最小生成树求无向图 G 的全部最小生成树的算法如下（1） 求最小生成树 比较成熟的算法，在此就不做介绍（2） 求约化图算法 （去掉基本回路中的唯一最长边）Step1 令为连枝集合，j=1；Step2 在 中加入连枝，形成一个基本回路，记为；Step 3 若 是基本回路中唯一最长边，则从图 G 中去掉；Step4 j =j +1,若 j 不大于 b，则返回Step2；Step5 输出经约化后的图 G。（3 ）求固定边算法 （保留基本割集中唯一的最短边）Step 1 令 E = , , 为最小生成树的树枝集合，S =，为树枝的基本割集，i=1;Step 2 从约化后的图 G 中求出树枝的基本割集；Step3 若 是基本割集 S 中的唯一最短边，则将 取为固定边，并对作记号； Step4 i 增加1, 若 i 不等于n, 则返回Step2（4） 求换入边算法（ 若基本割集中有记号，则为固定边，若没有记号，则从中求换入边）Step1 设 H 为换入边的集合，F 为换出边的集合，初始 H、F 为空，i=1；Step 2 若的基本割集 =中有记号，则 为固定边，执行Step 8；Step3 若的基本割集 中无记号，则 放入 F 中；Step4 令 k= 1；Step 5 若，且权，放入H中；Step6 k =k+ 1；Step7 若 k d （d 为 的长度，即中元素的个数） 则返回Step5；Step 8 i = i +1，若 i 小于或等于 n 1, 则返回Step 2（5） 求全部最小生成树算法 按距离从1到g 求全部最小生成树）设 H =为换入边的集合，F =为换出边的集合Step 1 若 H 为空，则最小生成树是唯一，输出，算法结束( )Step2 k =1, = , 输出 , （k 为距离） ；Step3 j =k；Step4 若, 且权，则在中用代替，输出（在已经换入 k 条边后的最小生成树中再换入，生成新的最小生成树）;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) 所示的最小生成树称基本回路是由树枝和一条连枝组成的回路，由“破圈法”的思想，若此连枝是基本回路中的唯一最长边，则将此边去掉后得到约化图无向图G的基本回路中的唯一最长边为：在基本回路-中有唯一最长边是，其权为7，将其去掉；在基本回路-中有唯一最长边是，其权为3，将其去掉；在基本回路-中有唯一最长边是，其权为4，将其去掉；在基本回路-中有唯一最长边是，其权为 8，将其去掉去掉基本回路中的唯一最长的边后，形成如图1 (c) 所示的约化图对无向图 G 进行约化后，最小生成树 中各边的基本割集为： ，为唯一最短边，取为固定边，将此割集作上记号；：， ；：，；：，为唯一最短边，取为固定边，将此割集作上记号；：， ，为唯一最短边，取为固定边，将此割集作上记号；：， ，为唯一最短边，取为固定边，将此割集作上记号在 中，取为固定边的有 ， 这样其他的最小生成树只能在 ， 和 ， 这两个基本割集中选取了根据算法，得到换入边为 ， ，换出边为 ， 当 k = 1 时，换入一条边得到的最小生成树W( )=w（），用边换得到最小生成树a，如图1（ d） 所示；w （） =w （），用换得到最小生成树b，如图1 （e ）所示； k =2 时，用换后，再用换得到的最小生成树c，如图1 （f） 所示 4 结论本文在对连通图的特征进行分析的基础上，得出在某个基本回路 C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边，将此边从无向图 G 中去掉，对图进行约化；若在某个边 e的割集中有一条唯一最短边，则每棵生成树中都必须含这条边，则取为固定边利用“破圈法”的思想去掉基本回路中的唯一最长边，保留基本割集中唯一最短边，对连通图进行约化，在约化图的基础上求全部最小生成树，计算量会大量地下降，算法的效率将大大地提高2. 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到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（0kn-1）？ Dk-1ij表示从i到j的中间点不大于k-1的最短路径p：ij， 考虑将顶点k加入路径p得到顶点序列q：ikj， 若q不是路径，则当前的最短路径仍是上一步结果：Dkij= Dk1ij； 否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。 因为q的两条子路径ik和kj皆是中间点不大于k1的最短路径，所以从i到j中间点不大于k的最短路径长度为： Dkijmin Dk-1ij, Dk-1ik +Dk-1kj Floyd算法实现： 可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就