算法设计与分析论文

1、任意结点间的最短路径方法的分析与研究摘要dijkstra算法是图论中的著名算法，可用于计算网络图中某一点到各点的最短距离，但实际问题中有时需要求网络中所有各点之间的最短距离，如果仍采用dijkstra算法分别计算，则需要对其执行多次，效率低。动态规划方法主要是研究与解决多阶段决策过程的最优化问题，也是求最短路问题的好算法。动态规划方法是将求解分成多阶段进行，求出的不但是全过程的解，而且包括后部子过程的一族解，在某些情况下，实际问题需要族解时，更显优越性。用动态规划方法求解最短路问题时，要求所求问题具有明显的阶段。本文分别讨论了这两种算法，论证了动态规划方法在求解所有结点之间最短距离问题的优越性

2、。关键字：最短路 dijkstra算法 动态规划 abstractdijkstra algorithm is a well-known algorithms in graph theory can be used to calculate the network diagram to a point in the shortest distance between points, but the real question to be asked sometimes all of the network the shortest distance between points, respect

3、ively, if the still use the dijkstra algorithm for computing , you need to perform several times and low efficiency. dynamic programming method is to study multi-stage decision-making process and resolving the optimization problem, find the shortest path problem is a good algorithm. solve the dynami

4、c programming approach is to be divided into multiple stages, find the only solution of the whole process, but also the process of the rear sub-family of solutions, in some cases, the family of solutions of practical problems, the more advantages. dynamic programming method for solving the shortest

5、path problem, ask the obvious question seeking stage. this paper discusses the two algorithms, dynamic programming method demonstrated in solving the shortest distance between all nodes in the superiority of the problem.keywords: shortet route , dijkstra algorithm, dynamic programming 1 引言生产实践，运输管理以

6、及工程建设的许多方面，诸如各种工艺路线的安排，厂区及货场 的布局，管道线网的铺设等问题，都与寻找一个图的最短路径问题密切相关。目前最短路径算法在智能系统的代价驱动搜索，神经元网络等研究领域也越来越受到重视。在这些研究中，不仅要寻找一个图的最短路径，而且要不断生成新图，不断寻找新的最短路径。先来看一下常见的问题：要从甲地到乙地去，而甲乙两地之间有多条交通线相连，这些交通线可以是公路、水路、铁路、航空线等，走哪条交通线才最好呢？这“最好”在不同的情况下有着不通过的含义，或者是距离最短，或者是时间最少，或者是旅费最省等，但抽象起来则都是在有向图中求两指定结点最短路径问题。设用一个带权的图来表示一个交

7、通运输网络，用图的顶点表示城市，用图中的各条边表示城市之间的交通运输路线，每条边上所附的权值表示该路线的长度或沿此路线运输所花费的时间或运费等。这种运输路线往往有方向性，例如汽车的上山和下山，轮船的顺水和逆水，所花费的时间或代价就不相同。所以交通运输网络往往是用带权有向图表示。所谓最短路径问题是指：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上个边上的权值和达到最小。2 贪心方法 有这样一类问题：它有n个输入，而它的解就由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件(约束条件)。把满足约束条件的子集称为该问题的可行解

8、。显然，满足约束条件的子集可能不止一个，因此可行解一般来说不是唯一的。为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以函数的形式给出，这些函数称为目标函数。使目标函数取极大值或极小值的可行解称为最优解。贪心方法是一种改进了的分级处理方法，它首先根据题意，选取一种量度标准。然后按这种量度标准对这n个输入排序，并按序依次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。要注意的是，对于一个给定的问题，往往可能有好几种量度标准。初看起来这些量度标准似乎都是可

9、取的。但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的解不一定是问题的最优解。因此，选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。在一般情况下，要选出最优量度标准并不是一件容易的事，不过，一旦能选择出某个问题的最优量度标准，那么用贪心方法求解这个问题则特别有效。贪心方法和动态规划的的主要区别是：贪心方法的每一步的最优解一定依赖上一步的最优解。而动态规划全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此动态规划需要记录之前的所有最优解。3 贪心策略的最短路径问题的提法是：给定一个带权有向图d与源点v，求从v到d中其他顶点的最短路径，若求所有顶

10、点之间的最短路径，则加一个外重循环，将每一个顶点依次作为源点考虑。为了求得这些最短路径，dijkstra提出了按路径长度的递增次序，逐步产生最短路径的算法。为了制定产生最短路径的贪心基础算法，对于这个问题应该相处一个多级解决办法和一种最优的量度标准。方法是构造这些最短路径，可以使用迄今已生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，其单独的每一条路径都必须具有最小长度。使用这一量度标准时，假定已经构造了i条最短路径，则下面要构造的禄纪念馆应该是下一条最短的最小程度路径。生成从v到所有其它结点的最短路径的贪心方法就是按照路径长度的非降次序生成这些路径。作为一个例子，考虑如图1所示的

11、带权有向图。边上的数字即为该边的长度，并设源点位顶点0。按照dijkstra算法，首先应用其邻接矩阵的第0行，求出从顶点0到其它各顶点最短路径的初步结果；以后逐步求最短路径的过程如图2所示。具体做法是：设集合s存放已经求出的最短路径的终点，初始状态时，集合s中只有一个源点，不妨设为v。以后每求得一条最短路径(v,v),就将v加入到集合s中，知道全部顶点都加入到集合s中算法就可以结束了。01423105020601003010(a) 带权有向图图1 带权有向图及其邻接矩阵表示 0 1 2 3 4(b) 邻接矩阵为了找到当前找到的从源点v到其它顶点的最短路径长度，再引入一个辅助数组dist。它的每

12、一个分量disti表示当前找到的从源点v到终点v的最短路径的长度。它的初始状态是：若从源点v到顶点v有边，则disti为该边上的权值；若从源点v到顶点v没有边，则disti为(在程序中用机器可表示的最大正数maxnum代表)。设一条最短路径为(v，v)，其中k满足： distk= 其中v是d的顶点集合源点终点最短路径路径长度图2 dijkstra算法逐步求解的过程vv(v, v)90v(v, v，v)(v, v，v)6050v(v, v )v(v, v) )(v, v，v)(v, v，v，v)10060那么下一最短路径是哪一条呢？ 假设下次最短路径的重点是v，则可想而知，它或者是(v,v),或

13、者是(v,v,v)，其长度或者是从v到v的有向边上的权值，或者是distk与从v到v的有向边上的权值之和。一般情况下，假设s是以求得的最短路径的终点的集合，则可以证明：下一条最短路径必然是从v出发，中间只经过s中的顶点便可到达的那些顶点v(vv-s)的路径中的一条。这可以用反证法证明。设在此路径上存在一个顶点vv-s，则说明还存在一条终点不再s而长度比此路径短的路径，然而这时不可能的。因为dijkstra方法是按照最短路径的长度递增的次序来逐次产生各条最短路径的，因此，长度比这条路径短的所有路径均已产生，而且它们的终点也一定已在集合s中，故假设不成立。因此在一般情况下，下一条长度次短的最短路径

14、长度必是： distk=在每一次求得一条最短路径之后，其终点v加入集合s，然后对所有的vv-s，修改其disti: disti=mindisti,distk+edgeki其中，edgeki是边(v,v)上的权值。上述方法只是求得了一个结点到所有的其他结点的最短距离，在此方法上对图中的每一个结点依次选取为源点，即可求出所有结点之间的最短路径。其总的时间复杂度为o(n)。此方法较为复杂，而且还存在一些问题，例如，假若从源点到某结点的有多条路，而且这几条路权值和相等，那么此时dijkstra算法将只会找到其中一条路，另外的路被舍去了，这在实际中会丢失参考一些的价值。下面将介绍另一种用动态规划的方法求

15、得所有结点之间最短路径的方法。4 动态规划我们在工作学习中，遇见过这样的问题，它的活动过程可以分为若干个阶段，而且在任一阶段后的行为都仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关，这样的过程就构成一个多阶段决策过程。50年代，贝尔曼等人根据这类问题的多阶段决策的特性，提出了解决这类问题的“最优性原理”，创建了最优化问题的一种新的算法设计方法-动态规划。动态规划的目标是要在所有容许选择决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨拙的方法。利用最优性原理以及所获得的递推关系式去求取最优决策序列

16、可以使枚举量急剧下降。这个原理指出：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果所求解问题的最优性原理成立，则说明用动态规划的方法有可能解决该问题，而解决问题的关键在于获取各阶段间的递推关系式。5 每对结点间最短路径的动态规划方法前面研究讨论了在dijkstra方法的基础上求得每对结点间的最短路径长度，就是轮流以每一个顶点为源点，重复执行dijkstra算法n次，就可求得每一对顶点之间的最短路径长度，总的执行时间是o(n)下面利用动态规划方法来设计这个问题的另一种算法，虽然它要求的计算时间仍是o(n),但在边成本上要求的约束条件要弱些

17、。它只要求图不含负长度的环即可，而不是要求图中所有的边权值都要是非负数。动态规划方法仍然使用前面定义的图的邻接矩阵edgenn来存储带权有向图。算法的基本思想是：设置一个nn的方阵a,其中除对角线的矩阵元素都等于0外，其它元素aij(ij)表示从顶点v到顶点v的有向路径长度，k表示运算步骤。初始时，以任意两个顶点之间的直接有向边的权值作为路径长度：对于任意两个顶点v和v，若它们之间存在有向边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以maxnum(机器可表示的在问题中不会遇到的最大数)作为它们之间的最短路径长度，因此a=edge。以后逐步尝试在原路径中加入其它顶点

18、作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素，代入新的更短的路径长度。如图3。从顶点v到顶点v的边的权值为5，当加入中间顶点v后，从v经过v再到v的权值之和为4，小于原来的权值5，则以此新路径的长度作为从顶点v到顶点v的距离, 并修改相应地矩阵元素。需要加以说明的是，考虑顶点v作为中间顶点可能还会改变其它顶点之间的距离，例如，路径的长度为7，小于原来有向边上的权值8，矩阵元素也要修改，这种修改会对以后的运算产生影响。如果在下一步又增加顶点v作为中间顶点，对于图中的每一条有向边,要比较从v到v的路径长度加上从v到v的路径长度是否小于原来

19、从v到v的路径长度，即+？如果小，又需用此新值代替原值作为元素的值。这时，从v到v的路径长度，以及从v到v的路径长度已经由于v作为中间顶点而修改过了，所以最新的值实际包含了顶点v，v，v，v的路径的长度。如上图3所示，元素在引入中间顶点v后，其值减为7，在引入中间顶点v后，其值又减为6。但有时加入中间顶点后的路径较原路径更长，这是就维持原来相应地矩阵元素的值不变。依此类推，可以得到如下的递推关系式：623014892130 1 2 3(a)(b)图3 带权有向图及其邻接矩阵定义一个n阶方阵序列：a，a，a，a，其中：a=edge；a=mina,a+a,k=0,1,n-1从上述公式可以得知，a是从顶点v到v，中间顶点是v的最短路径的长度，a是从顶点v到v，中间顶点的序号不大于k的最短路径的长度，那么最后a是从顶点v到v的最短路径长度。下图4为求解的矩阵的结果。aa0 1 2 3a0 1 2 3a0 1 2 3a0 1 2 30 1 2 3图4 动态规划方法矩阵a求解结果动态规划的最短路径方法允许图中带负权值的边，但不允许有包含带负权值的边组成的回路，此方法不仅适用于带权有向图，对带权无向图也可以使用，因为带权无向图可以看作是有往返