《算法设计与分析论文》由会员分享，可在线阅读，更多相关《算法设计与分析论文（8页珍藏版）》请在金锄头文库上搜索。
1、任意结点间的最短路径方法的分析与研究任意结点间的最短路径方法的分析与研究摘要摘要Dijkstra 算法是图论中的著名算法，可用于计算网络图中某一点到各点的最短距离， 但实际问题中有时需要求网络中所有各点之间的最短距离，如果仍采用 Dijkstra 算法分别 计算，则需要对其执行多次，效率低。动态规划方法主要是研究与解决多阶段决策过程的 最优化问题，也是求最短路问题的好算法。动态规划方法是将求解分成多阶段进行，求出 的不但是全过程的解，而且包括后部子过程的一族解，在某些情况下，实际问题需要族解 时，更显优越性。用动态规划方法求解最短路问题时，要求所求问题具有明显的阶段。本 文分别讨论了这两种算法
2、，论证了动态规划方法在求解所有结点之间最短距离问题的优越 性。关键字：最短路关键字：最短路 DijkstraDijkstra 算法算法 动态规划动态规划 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 n
3、etwork the shortest distance between points, respectively, 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 shorte
4、st path problem is a good algorithm. Solve the dynamic 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.
5、 Dynamic programming method for solving the shortest 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 , D
6、ijkstra Algorithm, Dynamic Programming 1 1 引言引言生产实践，运输管理以及工程建设的许多方面，诸如各种工艺路线的安排，厂区及货 场 的布局，管道线网的铺设等问题，都与寻找一个图的最短路径问题密切相关。目前最短 路径算法在智能系统的代价驱动搜索，神经元网络等研究领域也越来越受到重视。在这些 研究中，不仅要寻找一个图的最短路径，而且要不断生成新图，不断寻找新的最短路径。 先来看一下常见的问题：要从甲地到乙地去，而甲乙两地之间有多条交通线相连，这些交通线可以是公路、水路、铁路、航空线等，走哪条交通线才最好呢？这“最好”在不 同的情况下有着不通过的含义，或者是
7、距离最短，或者是时间最少，或者是旅费最省等， 但抽象起来则都是在有向图中求两指定结点最短路径问题。设用一个带权的图来表示一个 交通运输网络，用图的顶点表示城市，用图中的各条边表示城市之间的交通运输路线，每 条边上所附的权值表示该路线的长度或沿此路线运输所花费的时间或运费等。这种运输路 线往往有方向性，例如汽车的上山和下山，轮船的顺水和逆水，所花费的时间或代价就不 相同。所以交通运输网络往往是用带权有向图表示。所谓最短路径问题是指：如果从图中 某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使 得沿此路径上个边上的权值和达到最小。2 2 贪心方法贪心方法有这样一类
8、问题：它有n个输入，而它的解就由这n个输入的某个子集组成，只是这个 子集必须满足某些事先给定的条件(约束条件)。把满足约束条件的子集称为该问题的可行 解。显然，满足约束条件的子集可能不止一个，因此可行解一般来说不是唯一的。为了衡 量可行解的优劣，事先也给出了一定的标准，这些标准一般以函数的形式给出，这些函数 称为目标函数。使目标函数取极大值或极小值的可行解称为最优解。 贪心方法是一种改进了的分级处理方法，它首先根据题意，选取一种量度标准。然后 按这种量度标准对这n个输入排序，并按序依次输入一个量。如果这个输入和当前已构成在 这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到
9、这部分解 中。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。要注意的是， 对于一个给定的问题，往往可能有好几种量度标准。初看起来这些量度标准似乎都是可取 的。但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的解不一定是问 题的最优解。因此，选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心 问题。在一般情况下，要选出最优量度标准并不是一件容易的事，不过，一旦能选择出某 个问题的最优量度标准，那么用贪心方法求解这个问题则特别有效。 贪心方法和动态规划的的主要区别是：贪心方法的每一步的最优解一定依赖上一步的 最优解。而动态规划全局最优解中一定包含某个局部最优解
10、，但不一定包含前一个局部最 优解，因此动态规划需要记录之前的所有最优解。3 3 贪心策略的最短路径贪心策略的最短路径问题的提法是：给定一个带权有向图D与源点v，求从v到D中其他顶点的最短路径，若 求所有顶点之间的最短路径，则加一个外重循环，将每一个顶点依次作为源点考虑。 为了求得这些最短路径，Dijkstra提出了按路径长度的递增次序，逐步产生最短路径 的算法。为了制定产生最短路径的贪心基础算法，对于这个问题应该相处一个多级解决办 法和一种最优的量度标准。方法是构造这些最短路径，可以使用迄今已生成的所有路径长 度之和作为一种量度，为了使这一量度达到最小，其单独的每一条路径都必须具有最小长 度。
11、使用这一量度标准时，假定已经构造了i条最短路径，则下面要构造的禄纪念馆应该是下一条最短的最小程度路径。生成从v 到所有其它结点的最短路径的贪心方法就是按照路0径长度的非降次序生成这些路径。 作为一个例子，考虑如图1所示的带权有向图。边上的数字即为该边的长度，并设源点 位顶点0。按照dijkstra算法，首先应用其邻接矩阵的第0行，求出从顶点0到其它各顶点最短路径的初步结果；以后逐步求最短路径的过程如图2所示。 具体做法是：设集合S存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点，不妨设为v 。以后每求得一条最短路径(v0,v ),就将v 加入到集合S中，知0kk道全部顶点都加入到
12、集合S中算法就可以结束了。01423105020601003010(a) 带权有向图图 1 带权有向图及其邻接矩阵表示0 1 2 3 40600201005001003010043210(b) 邻接矩阵为了找到当前找到的从源点v 到其它顶点的最短路径长度，再引入一个辅助数组0dist。它的每一个分量disti表示当前找到的从源点v 到终点v 的最短路径的长度。它0i的初始状态是：若从源点v 到顶点v 有边，则disti为该边上的权值；若从源点v 到顶0i0点v 没有边，则disti为(在程序中用机器可表示的最大正数MAXNUM代表)。i设一条最短路径为(v ，v )，其中k满足：0kdistk
13、= 其中V是D的顶点集合| min0vVvidistii源点终点最短路径路径长度图 2 Dijkstra 算法逐步求解的过程v0v1(v , v )01)90v2(v , v ，v )012)(v , v ，v )032)6050 v3(v , v )03)v4(v , v)04)(v , v ，v)034)(v , v ，v ，v)0324)10060那么下一最短路径是哪一条呢？ 假设下次最短路径的重点是v ，则可想而知，它或者是j(v ,vj),或者是(v0,v ,v )，其长度或者是从v 到v 的有向边上的权值，或者是0kj0jdistk与从v 到v 的有向边上的权值之和。kj一般情况下
14、，假设S是以求得的最短路径的终点的集合，则可以证明：下一条最短路径必然是从v 出发，中间只经过S中的顶点便可到达的那些顶点v (vV-S)的路径中的一0xx条。这可以用反证法证明。设在此路径上存在一个顶点vV-S，则说明还存在一条终点不再S而长度比此路径短p的路径，然而这时不可能的。因为dijkstra方法是按照最短路径的长度递增的次序来逐次产生各条最短路径的，因此，长度比这条路径短的所有路径均已产生，而且它们的终点也一定已在集合S中，故假设不成立。因此在一般情况下，下一条长度次短的最短路径长度必是：distk=| minSVvidistii在每一次求得一条最短路径之后，其终点v 加入集合S，
15、然后对所有的vV-S，修改ki其disti: disti=mindisti,distk+Edgeki其中，Edgeki是边(v ,v )上的权值。ki上述方法只是求得了一个结点到所有的其他结点的最短距离，在此方法上对图中的每一个结点依次选取为源点，即可求出所有结点之间的最短路径。其总的时间复杂度为O(n )。3此方法较为复杂，而且还存在一些问题，例如，假若从源点到某结点的有多条路，而且这 几条路权值和相等，那么此时Dijkstra算法将只会找到其中一条路，另外的路被舍去了， 这在实际中会丢失参考一些的价值。下面将介绍另一种用动态规划的方法求得所有结点之间最短路径的方法。4 4 动态规划动态规划
16、我们在工作学习中，遇见过这样的问题，它的活动过程可以分为若干个阶段，而且在 任一阶段后的行为都仅依赖于 i 阶段的过程状态，而与 i 阶段之前的过程如何达到这种状 态的方式无关，这样的过程就构成一个多阶段决策过程。50 年代，贝尔曼等人根据这类问 题的多阶段决策的特性，提出了解决这类问题的“最优性原理” ，创建了最优化问题的一种 新的算法设计方法-动态规划。 动态规划的目标是要在所有容许选择决策序列中选取一个会获得问题最优解的决策序 列，即最优决策序列。用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最 笨拙的方法。利用最优性原理以及所获得的递推关系式去求取最优决策序列可以使枚举量 急剧下降。这个原理指出：无论过程的初始状态和初始决策是什么，其余的决策都必须相 对于初始决策所产生的状态构成一个最优决策序列。如果所求解问题的最优性原理成立，
