最短路径问题的几个算法

作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径。 % X7 a5 a0 e2 `1 @! e0 F 算法如下：

1、 把上述邻接矩阵直接赋值给最短距离矩阵D； - n9 o) r( a9 s% _- o7 } 2、 i=1; 0 c& w% z% m& w l4 x+ [% t 3、 j=1； 1 h* M\ 4、 repeat

5、 c=false; {用以判断第6步是否有某个Dij值被修改过} ) D, F6 F k( A 6、 Dij=min(Dij,Dik+Dkj，……), k=1 to 5 如果Dij被修改则c=true 7、 I=I+1 8、 J=j+1 9、 Until not c

10、 打印D15 $ j2 T, S) ?8 k0 b/ b6 Q& d! x

这种算法是产生这样一个过程：不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。 , D8 Q& j\ 五、动态规划 ! J O) z( i `; p- @

动态规划算法已经成为了许多难题的首选算法，只不过在很多的题目中动态规划的算法表达式比较难找准，而恰恰最短距离问题如果用动态规划算法考虑则可以非常容易地找准那个算法表达式。

我们知道，动态规划算法与递归算法的不同之处在于它们的算法表达式：

递归：类似f(n)=x1*f(n-1)+x2*f(n-2)………，即可以找到一个确定的关系的表达式； 3 T; ]8 E% R\ c4 d( I; {% C

动态规划：类似f(n)=min(f(n-1)+x1,f(n-2)+x2……)，即我们无法找到确定关系的表达式，只能找到这样一个不确定关系的表达式，f(n)的值是动态的，随着f(n-1),f(n-2)等值的改变而确定跟谁相关。

就本题来说，我们记f(5)为A到E点的最短距离，则f(4)为A到D点的最短距离，f(1)为A到A点的最短距离（为0）。

于是，f(5)的值应该是所有与E点相邻的点的最短距离值再加上该点到E点的直接距离（dis矩阵中的值）所得到的值中最小的一个。 我们可以得到这样一个关系式： 7 j( {' m7 X* I5 \\. t1 ]6 X

f(5)=min(f(1)+dis(1,5), f(2)+dis(2,5), f(3)+dis(3,5), f(4)+dis(4,5))

以此关系式作一个递归函数即可求得A到E点的最短距离。不过，为了节省时间，我们可以把f(1)-f(4)已经算得的结果保存起来给后面的递归直接调用，这样就能节约大量的递归空间和时间，这对于数据量大时尤为重要。

关于最短路径问题还有以下几种算法： 一.最小生成树算法（破圈法） 1 理论根据 1.1 约化原则

给定一无向连通图 G =（V,E）（ V 表示顶点，E表示边），其中 V={ v1 ,

v2,v3…… vn },E= { e1 , e2, e3 …… en }对于 G 中的每条边 e ? E都赋予

权?（ei ）>0，求生成树 T = （V,H），H ? E，使生成树所有边权最小，此

生成树称为最小生成树． （1） 基本回路

将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为cf(e)。

基本回路是由 T 中的树枝和一条连枝构成的回路． （2） 基本割集

设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T中的一条树枝，则称此割集为基本割集，记为S(e)。

基本割集是集合中的元素只有一条是树枝，其他的为连枝． （3） 等长变换

设T=(V,H),为一棵生成树，e ? H, e'? E, e' ? H,当且仅当e'?cf(e)，也就是说e ?S(e)，则T'=T?{e, e'}也是一棵生成树。当?(e)=?(e')时，这棵生成树叫做等长变换。

等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树．

根据以上定理得出2个结论：①若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边．由上面结论可以得到唯一性：若图 G 中的生成树T = （V,H）是唯一的一棵最小生成树，当且仅当任意一连枝e ? H,

e? E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集S(e)'中

的唯一最短边．

由此在最小生成树不唯一的情况下，就可以得到一个约化的原则：假设已得到一棵最小生成树T0。对于T0中每一条树边e ? H，若 e 是基本割集S(e)中唯一的最短边，则每棵最小生成树中一定包含此边，则把此边取为固定边，并将此边的基本割集去掉。

对于每条连枝e ? H, e'? E，若它是基本回路cf(e)中唯一最长边，则每棵生成树中都不会包含此条连枝，则将其消去．

约化原则是在最小生成树不唯一的情况下，从已经得到的一棵最小生成树

T0中选出其树枝是基本割集中唯一的最短边，则每一棵最小生成树中必含有此

边，就取为固定边．在基本回路中若有一条唯一最长边，则每棵最小生成树都不含此条边，将其去掉．通过这样约化后再求最小生成树，计算量会大大下降．

1.2 全部最小生成树

设T0是已求得的一棵最小生成树，在最小生成树不唯一的情况下，存在其他最小生成树 T，称T-T0得到的边集的长度为距离（这里的长度是指集合中元素的个数）。

为了简单起见，设最小生成树T0的边集为{ e1 , e2, e3 ……en?1}，对于T0的任何边集Hk={ e1 , e2, e3 ……ek?1}（1?k?n?1），则每棵最小生成树 T 与

T0的距离是一定的，或为1，或为

2 ，或为 n -1．这样我们就可以按所有的最

小生成树与T0的距离来分类。

记Ti1,i2,……ik={ e1 , e2, e3 ……ek?1}为所有的T0—Hk即不含Hk的最小生成树的集合（可能为空）．对于其它的最小生成树T?Ti1,i2,……ik而言，Hk=T0—T为换出边，Hk=T—T0为入边，T0?T中的边叫不动边．若 T 有 k 个换出边就说它与T0的距离为 k．当 k=0 时为参考树本身。