最短路径学年论文

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和

12、j之间的可实现的距离，那么表示端i和j之间的最短距离当且仅当对于任意的i, j, k，有。该算法用矩阵形式来表示，并进行系统化的计算，通过迭代来消除不满足上述定理的情况，对于n个端，一给定边长的图，顺序计算各个的w阵和r阵，前者代表径长，后者代表转接路由。其步骤如下：置 其中 和 其中 ：已得和阵，求和阵中的元素如下 ：，重复；，终止。由上述步骤可见，是计算经转接时是否能缩短经常，如有缩短，更改并在r阵中记下转接的端。最后算得和，就得到了最短径长和转接路由。4.3 floyd算法实例 假设某旅游路线的赋权图如下：7264113541441126699 图4 某旅游路线赋权图现在我们以上述生成的

13、图4为考察对象，根据算法流程，设w阵和r阵分别代表路径长和转接路由。那么计算结果如下： 经过7轮迭代，我们得到了最终的w和r阵，分别包含了径长信息和路由信息。我们可以从和中找到任何两个端点间的最短径长和最短路由，对应着我们所建立的旅行线路模型中的任何两景点间的最短路径长度和路线。 若要求旅游点3到点1的最短路径，则可以从中找到对应的最小值为18，从中找到，就是要经点2转接；再看，此时已经到达目的节点，所以路由是。5 dijkstra算法和floyd算法在求最短路径的异同相同： 是按路径长度递增的思路进行查找最短路径。 都需要借助带权领接矩阵； 都引进了辅助数组； floyd法的替代算法是n次调

14、用dijkstra法（n为图g中结点数目）。 相异： dijkstra算法是从一点出发到其余路径的最短路径，而floyd算法是找图中所有顶点间的最短路径； dijkstra算法是找到最短后再尝试利用该最短辅助找其余最短的；而floyd算法是在插入第i-1个顶点的基础上比较插入第i个后和之前的最短； 路径长度递增不一样：dijkstra算法增的路径是比较出最短的增，而floyd算法增的路径是按编号递增； dijkstra算法从源点出发，而弗法可以从任意点出发； 结果不同，dijkstra算法找到的是从源点到其余顶点的最短路径；floyd算法则可以求任两点之间的最短路径。6 利用计算机程序模拟算法

15、对于图g来说，如果g中的结点个数较少，可以通过逐步迭代或者通过以上的列表形式算出不同点之间的最短路径，但相对于结点数目较多的图而言，显得力不从心，也大大增加了计算过程中的失误率。这个时候，我们就迫切希望寻求算学工具来解决人工的局限性。为此引入matlab来简化求解步骤，通过输入邻接矩阵和始末点来快速计算最短路径的值，并导出途经各结点。 其中dijkstra算法中的例子，可以另对应于标号，邻接矩阵为a，通过调用matlab功能函数可迅速得出最优路径及相关途经点。程序见附录。7 附录dijkstra算法：function d,path=dijkstra(w,s,t)n,m=size(w);ix=(

16、w=0);w(ix)=inf;if n=m,error(square w required);endvisited(1:n)=0; dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;for i=1:(n-1), ix=(visited=0);vec(1:n)=inf;vec(ix)=dist(ix); a,u=min(vec);visited(u)=1; for v=1:n,if (w(u,v)+dist(u)dist(v), dist(v)=dist(u)+w(u,v);parent(v)=u; end;end;endif parent(t)=0,path=t;d=dist(t); while t=s,p=parent(t);path=p path;t=p;end;endfloyd算法：function d,r=floyd(a) n=size(a,1); d=a; for i=1:n for j=1:n r(i,j)=j; end end r for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k) end end end k d r end8论文总