《最短路径毕业论文》由会员分享，可在线阅读，更多相关《最短路径毕业论文（9页珍藏版）》请在金锄头文库上搜索。
1、安庆师范学院数学与计算数学学院2013届毕业论文最短路算法的比较与应用作者：胡义棚 指导老师：丁超摘要：本文较详尽地介绍了最短路算法相关的基本概念，给出了Dijkstra算法、Floyd算法、SPFA算法等常用算法及其核心思想，并对各种最短算法做了多角度的比较，阐述了各种算法的应用范围，并对其在运输网络、舰船通道路线设计、工业生产中的应用做出了举例说明，侧重于模型的建立、思考和证明的过程，最后作出总结.关键词：最短路算法 Dijkstra算法 Floyd算法 SPFA算法 一、引言 最短路算法是图论中的核心问题之一，他是许多更深层次算法的基础，同时，该问题有着大量的生产实际的背景.很多问题从表
2、面上看与最短问题没有什么关系.却也可以归结为最短路问题，本文通过收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题，工程问题，及实际生活问题中的应用，为企业和个人提供方便的选择方法.二、最短路2.1 最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路.后来海斯在Dijkstra算法的基础之上提出了海斯算法.但这两种算法都不能解决含有负权的图的最短路问题.因此由Ford提出了Ford算法,它能有效地
3、解决含有负权的最短路问题.但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法定义1 若图中各边e都赋有一个实数,称为边的权,则称这种图为赋权图,记为.定义2 若图是赋权图且,若u是到的路的权,则称为的长,长最小的到的路称为最短路.若要找出从到的通路,使全长最短,即.2.2 各类最短路算法的介绍2.2.1 Floyd算法 Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法.该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名. 其核心思路是通过一个图的权值矩阵求出它的每两点间的最
4、短路径矩阵.即从图的带权邻接矩阵开始，递归地进行n次更新，即由矩阵，按一个公式，构造出矩阵；又用同样地公式由构造出；最后又用同样的公式由构造出矩阵.矩阵的行列元素便是号顶点到号顶点的最短路径长度，称为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径. 下面介绍其算法过程： 从任意一条单边路径开始.所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大;对于每一对顶点和 ，看看是否存在一个顶点使得从到再到比已知的路径更短.如果是更新它;把图用邻接距阵表示出来，如果从到有路可达，则,表示该路的长度；否则为无穷大;定义一个距阵用来记录所插入点的信息，表示从到需要经过
5、的点，初始化;把各个顶点插入图中，比较插点后的距离与原来的距离， ，如果的值变小，则;在中包含有两点之间最短道路的信息，而在中则包含了最短通路径的信息.2.2.2 Dijkstra算法9612345 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等.Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用
6、永久和临时标号的方式.注意该算法要求图中不存在负权边.812115101516147下面介绍其算法过程：首先，引进一个辅助向量，它的每个分量表示当前所找到的从始点到每个终点的最短路径的长度.如表示从始点v到终点3的路径相对最小长度为2.这里强调相对就是说在算法过程中的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度.它的初始状态为：若从到有弧，则为弧上的权值；否则置为.显然，长度为 的路径就是从出发的长度最短的一条最短路径.此路径为.那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是，则可想而知，这条路径或者是，或者是.它的长度或者是从v到vk的弧上的权值，或者是和从到的
7、弧上的权值之和. 一般情况下，假设为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为）或者是弧，或者是中间只经过S中的顶点而最后到达顶点的路径.因此，下一条长度次短的最短路径的长度必是 其中，或者是弧上的权值，或者是和弧上的权值之和. 迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值.若不存在，则置arcs为.为已找到从v出发的最短路径的终点的集合，初始状态为空集.那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为 ,使得修改从出发到集合上任一顶点可达的最短路径长度. 2.2.3 Bellman-Ford算法Dijkstra算法中不允许边的权是负权，如果遇到负
8、权，则可以采用Bellman-Ford算法.Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题.对于给定的带权（有向或无向）图 ，其源点为，加权函数 是 边集 的映射.对图运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点可达的负权回路.若不存在这样的回路，算法将给出从源点到 图的任意顶点的最短路径.下面介绍其算法过程：初始化：将除源点外的所有顶点的最短距离估计值 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集中的每个顶点的最短距离估计值逐步逼近其最短距离（运行次）；检验负权回路：判断边集中的每一条边的两个端点是否收敛.如
9、果存在未收敛的顶点，则算法返回，表明问题无解；否则算法返回，并且从源点可达的顶点的最短距离保存在中.2.2.4 SPFA算法求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm.SPFA算法由西南交通大学段凡丁于1994年发表.很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了. 下面介绍其原理与算法过程：我们约定有向加权图不存在负权回路，即最短路径一定存在.当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路.我们用数组记录每个结点的最短
10、路径估计值，而且用邻接表来存储图.我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点，并且用点当前的最短路径估计值对离开点所指向的结点进行松弛操作，如果点的最短路径估计值有所调整，且点不在当前的队列中，就将点放入队尾.这样不断从队列中取出结点来进行松弛操作，直至队列空为止.每次将点放入队尾，都是经过松弛操作达到的.换言之，每次的优化将会有某个点的最短路径估计值变小.所以算法的执行会使越来越小.由于我们假定图中不存在负权回路，所以每个结点都有最短路径值.因此，算法不会无限执行下去，随着值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应
11、结点的最短路径值. 所以只要最短路径存在，上述SPFA算法必定能求出最小值. 2.3 最短算法的比较2.3.1 Floyd 算法 求多源、无负权边的最短路.用矩阵记录图.时效性较差，时间复杂度. Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题.Floyd-Warshall算法的时间复杂度为空间复杂度为 Floyd-Warshall的原理是动态规划：设为从i到j的只以(1.k)集合中的节点为中间节点的最短路径的长度.若最短路径经过点，则 若最短路径不经过点，则 因此，Dijkstra
12、 求单源、无负权的最短路.时效性较好，时间复杂度为.源点可达的话，.当是稀疏图的情况时，此时/，所以算法的时间复杂度可为 .若是斐波那契堆作优先队列的话，算法时间复杂度，则为. Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度.Bellman-Ford算法是求解单源最短路径问题的一种算法. 单源点的最短路径问题是指：给定一个加权有向图和源点，对于图中的任意一点，求从到的最短路径. 与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数. 设想从我们可以从图中找到一个环路（即从出发，经过若干个点之后又回到）
13、且这个环路中所有边的权值之和为负.那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去.如果不处理这个负环路，程序就会永远运行下去. 而Bellman-Ford算法具有分辨这种负环路的能力.SPFA 是Bellman-Ford的队列优化，时效性相对好，时间复杂度.与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径.所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数. SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同
14、的.与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别. 在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为另一方面，存在这样的例子，使得每一个节点都被入队次，此时算法退化为Bellman-ford算法，其时间复杂度为. SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好.但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本.通常的SPFA算法在一类网格图中的表现不尽如人意.完.
15、2.4最短路算法的应用在运输网络中的应用设6个城市之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市,那么从到应选择哪一路径使你的费用最省.5255521210解:首先设每百公里所用费用相同,求到的费用最少,既求到的最短路线.为了方便计算,先作出该网络的距离矩阵,如下:(0)设,(1)第一次迭代计算如下取,令由于,令转(1)第二次迭代:算如下取令由于,令转(1)第三次迭代:算如下取由于,令转第四次迭代:算如下取由于,令转(1)第五次迭代:算如下由于.因此已找到到的最短距离为12.计算结束.找最短路线:逆向追踪得最短距离为,即从城市到城市的距离最短,即费用最省.在舰船通道路线设计中的应用利用图论的经典理论和人群流量理论研究舰船人员通道路线的优化设计及最
