《最短路径学年论文》由会员分享，可在线阅读，更多相关《最短路径学年论文（19页珍藏版）》请在金锄头文库上搜索。
1、摘要：主要介绍最短路径问题中的经典算法迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab目录摘要11引言12最短路22.1 最短路的定义 22.2最短路问题常见算法23 Dijkstra算法23.1 Dijkstra算法描述23.2 Dijkstra算法举例33.3算法的正确性和计算复杂性53.3.1贪心选择性质53.3.2最优子结构性质63.3.3 计算复杂性74 Floyd算法74.1Floyd算法描述84.2 Floyd算法步骤114.3 Floyd算法举例115 Dijks
2、tra算法和Floyd算法在求最短路的异同116 利用计算机程序模拟算法117 附录118 论文总结139 参考文献131 引言 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。2 最短路2.1 最短路的定义对最短路问题的研究早在
3、上个世纪60年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的的情况下选择Dijkstra算法。定义1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。定义2若
4、图G=G(V,E)是赋权图且,假设i,j 的权记为,若i与j之间没有边相连接，那么。路径P的定义为路径中各边的长度之和，记W（P）。图G的结点u到结点v距离记为，则u、v间的最短路径可定义为。2.2 最短路问题常见算法在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。Dijkstra算法是图论中确定最短路的基本方法,也是其它
5、算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为,虽然与重复执行Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。3 Dijkstra算法3.1 Dijkstra算法描述Dijkstra算法是解但愿最短路径问题的一个贪心算法。其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是图G的某一顶点，把从源到u
6、且中间只经过S中顶点的路称为源到u的特殊路径，并记录当前每个顶点所对应的特殊路径长度。Dijkstra算法每次从VS中取出具有最短路径长度的顶点u，将u添加到S中，同时对短路径进行修改。一旦S包含了所有V中顶点，那么最后记录的最短路径就是源到所有其他顶点之间的最短路径长度。算法要点如下：（1） 把V分为两个子集S和T。初始时，S=a，T=V-S，其中a为源点；（2） 对T中每一个元素t计算D（t），根据D（t）值找出T中距a最短的一结点x，写出a到x的最短路径长度D（x）；（3） 更新S，置S为Sx，更新T，置T为T-x，判断条件：若T=，则终止，否则再重复（2）。3.2 Dijkstra算法
7、举例 问题的提出，给定一个带权有向图（既有向网）G和源点Vo，求Vo到G中其他每个顶点的最短路径。限定各边上的权值必须不小于0.如下图所示：12555581022 图1 公路网络赋权图为了方便计算,先作出该网络的距离邻接矩阵,如下:设,第一次迭代计算如下取,令由于,令转(1)第二次迭代:算如下取令由于,令转(1)第三次迭代:算如下取由于,令转(1)第四次迭代:算如下取由于,令转(1)第五次迭代:算如下由于。因此已找到到的最短距离为12。计算结束。对应的迭代表格如下：迭代su115（2）21,3（3）2101231,3,232（8）1241,3,2,4328（12）1551,3,2,432812
8、（12）找最短路线:逆向追踪得最短距离为12,即从城市到城市的距离最短,即费用最省。3.3算法的正确性和计算复杂性3.3.1贪心选择性质Dijkstra算法是贪心算法策略的一个典型例子。它所做的贪心选择是从VS中选择具有最短特殊路径的顶点u，从而确定从源到u的最短路径长度。这种贪心选择导致最优解在于如果存在一条源到u且长度比更短的路，设这条路初次走出S之外到达的顶点，然后徘徊于S内外若干次，最后离开S到达u，如图2所示。在这条路径上，分别标记，和为顶点v到顶点x，顶点x到顶点u和顶点v到顶点u的路长，那么有：u 利用权边的非负性，可知，从而推出。此为矛盾。这就证明了是从源点到u的最短路径长度。
9、源 Svx 图2 从源到u的最短路径3.3.2最优子结构性质要完成Dijkstra算法正确性的证明，还必须证明最优子结构性质，即算法中确定的确实是当前从源到顶点u的最短特殊路径长度。为此，只要考察算法在添加u到S中后，的值所起的变化。将添加u之前的S成为老S。当添加了u之后，可能出现一条到顶点i的新的特殊路。如果这条新特殊路是先经过老S到达顶点u，然后从u经一条边直接到达顶点i，则这种路的最短的长度是。此时如果，则计算中用作为disti的新值。如果这条新特殊路径经过老S到达u后，不是从u经过一条边直接到达i，而是像图3那样，回到老S中某个顶点x，最后才到达顶点i，那么由于x在老S中，因此x比u
10、先加入S，所以图3中从源到x的路的长度比从源到u，再从u到x的路的长度小。于是当前的值小于从源经x到i的路的长度，也小于图中从源经u和x，最后到达i的路的长度。因此，在计算中不必考虑这种路。由此可知，不论算法中的值是否发生变化，它总是关于当前顶点集S到达u的最短特殊路径长度。i老S源xvu图3 非最短路径的特殊路径3.3.3 计算复杂性对于一个具有n个顶点和e条带权边的图来说，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要的时间。这个循环体需要执行n-1次，所以完成循环需要时间。算法的其余部分所需要的时间不超过。4 Floyd算法4.1 Floyd算法描述Floyd算法又
11、称距离矩阵法,算法主要是寻找加权图中任意两个结点间最短路径的算法。其基本思想是：两结点间的最短路径要么是相邻时最短，要么是以通过几个中间结点为跳板时距离最短。算法每次以其中一个结点为跳板，如果以该结点为跳板后两结点间路径缩短，则更新这两结点间的路径。算法执行n次结束，直到测试完每个充当跳板的结点。若用Dijkstra算法计算任意两点间的最短路径，需要执行n次，且图中含有负权值时不能用Dijkstra算法。Floyd算法只能求出两点间最短路径的长度，无法得到这条最短路径，当然，如果记录了每步更新所经过的中间结点，仍可通过回溯得到两点间的最短路径。4.2 Floyd算法步骤 对于图G，如果表示i和j之间的可实现的距离，那么表示端i和j之间的最短距离当且仅当对于任意的i, j, k，有。该算法用矩阵形式来表示，并进行系统化的计算，通过迭代来消除不满足上述定理的情况，对于n个端，一给定边长的
