最短路径学年论文

-1-摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab目录摘要·······························································11引言······························································12最短路····························································22.1最短路的定义··············································22.2最短路问题常见算法···········································23Dijkstra算法······················································23.1Dijkstra算法描述·············································23.2Dijkstra算法举例·············································33.3算法的正确性和计算复杂性······································53.3.1贪心选择性质·············································53.3.2最优子结构性质···········································63.3.3计算复杂性··············································74Floyd算法·························································74.1Floyd算法描述·················································84.2Floyd算法步骤················································114.3Floyd算法举例················································115Dijkstra算法和Floyd算法在求最短路的异同··························116利用计算机程序模拟算法·············································117附录·······························································118论文总结···························································139参考文献···························································13-2-1引言最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。2最短路2.1最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的0ijw的情况下选择Dijkstra算法。定义1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。定义2若图G=G(V,E)是赋权图且0We,eEG,假设[i,j]的权记为ijW，,若i与j之间没有边相连接，那么ij=W，。路径P的定义为路径中各边的长度之和，记W（P）。图G的结点u到结点v距离记为d(u,v)，则u、v间的最短路径可定义为minP0d(u,v)=,uvW（），不可达时。2.2最短路问题常见算法在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。Dijkstra算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为3On,虽然与重复执行Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。3Dijkstra算法3.1Dijkstra算法描述-3-Dijkstra算法是解但愿最短路径问题的一个贪心算法。其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是图G的某一顶点，把从源到u且中间只经过S中顶点的路称为源到u的特殊路径，并记录当前每个顶点所对应的特殊路径长度。Dijkstra算法每次从V—S中取出具有最短路径长度的顶点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为S{x}，更新T，置T为T-{x}，判断条件：若T=，则终止，否则再重复（2）。3.2Dijkstra算法举例问题的提出，给定一个带权有向图（既有向网）G和源点Vo，求Vo到G中其他每个顶点的最短路径。限定各边上的权值必须不小于0.如下图所示：图1公路网络赋权图为了方便计算,先作出该网络的距离邻接矩阵,如下:12345612345605250159A21081058025910202520vvvvvvvvvvvv设1234560,,,,,,jWvTvvsvvvvv,1v2v3v4v5v6v12555581022-4-第一次迭代①计算,2,3,4,5,6jTvj如下22112min,min,055TvTvWvw33113min,min,022TvTvWvw44114min,min,0TvTvWvw56,TvTv②取32minjjvsTvTv,令332WvTv③由于36kn,令2456,,,,3svvvvi转(1)第二次迭代:①算,2,4,5,6jTvj如下22323min,min5,213TvTvWvw44334min,min8,288TvTvWvw55335min,min10,21010TvTvWvw66336min,min,2TvTvWvw②取2min3jjvsTvTv令223WvTv③由于26kn,令456,,2svvvi转(1)第三次迭代:①算,4,5,6jTvj如下44224min,min8,358TvTvWvw55225min,min10,3910TvTvWvw6Tv②取444min8,8jjvsTvTvWvTv-5-③由于46kn,令56,4svvi转(1)第四次迭代:①算,5,6jTvj如下55445min,min10,2810TvTvWvw66446min,min,8513TvTvWvw②取555min10,10jjvsTvTvWvTv③由于56kn,令6sv转(1)第五次迭代:①算,6jTvj如下66556min,min13,10212TvTvWvw②由于6kn。因此已找到1v到6v的最短距离为12。计算结束。对应的迭代表格如下：迭代su2v3v4v5v6v1{1}—5（2）2{1,3}3v（3）210123{1,3,2}2v32（8）124{1,3,2,4}4v328（12）155{1,3,2,4}5v32812（12）找最短路线:逆向追踪得132456vvvvvv最短距离为12,即从城市1v到城市6v的距离最短,即费用最省。3.3算法的正确性和计算复杂性3.3.1贪心选择性质Dijkstra算法是贪心算法策略的一个典型例子。它所做的贪心选择是从V—S中选择具有最短特殊路径的顶点u，从而确定从源到u的最短路径长度dist[u]。这种贪心选择导致最-6-优解在于如果存在一条源到u且长度比dist[u]更短的路，设这条路初次走出S之外到达的顶点xVS—，然后徘徊于S内外若干次，最后离开S到达u，如图2所示。在这条路径上，分别标记d(v,x)，d(x,u)和d(v,u)为顶点v到顶点x，顶点x到顶点u和顶点v到顶点u的路长，那么有：dist[x]d(v,x)d(v,x)+d(x,u)=d(v,u)dist[u]利用权边的非负性，可知d(v,x)0，从而推出dist[x]dist[u]。此为矛盾。这就证明了dist[u]是从源点到u的最短路径长度。图2从源到u的最短路径3.3.2最优子结构性质要完成Dijkstra算法正确性的证明，还必须证明最优子结构性质，即算法中确定的dist[u]确实是当前从源到顶点u的最短特殊路径长度。为此，只要考察算法在添加u到S中后，dist[u]的值所起的变化。将添加u之前的S成为老S。当添加了u之后，可能出现一条到顶点i的新的特殊路。如果这条新特殊路是先经过老S到达顶点u，然后从u经一条边直接到达顶点i，则这种路的最短的长度是dist[u]+c[u][i]。此时如果dist[u]+c[u][i]dist[i]，则计算中用dist[u]+c[u][i]作为dist[i]的新值。如果这条新特殊路径经过老S到达u后，不是从u经过一条边直接到达i，而是像图3那样，回到老S中某个顶点x，最后才到达顶点i，那么由于x在老S中，