最短路径毕业论文.doc

安庆师范学院数学与计算数学学院 2013 届毕业论文最短路算法的比较与应用作者:胡义棚指导老师:丁超摘要: 本文较详尽地介绍了最短路算法相关的基本概念,给出了 Dijkstra 算法、 Floyd 算法、 SPF A 算法等常用算法及其核心思想,并对各种最短算法做了多角度的比较,阐述了各种算法的应用范围,并对其在运输网络、舰船通道路线设计、工业生产中的应用做出了举例说明,侧重于模型的建立、思考和证明的过程,最后作出总结. 关键词: 最短路算法 Dijkstra 算法 Floyd 算法 SPFA 算法一、引言最短路算法是图论中的核心问题之一, 他是许多更深层次算法的基础, 同时, 该问题有着大量的生产实际的背景. 很多问题从表面上看与最短问题没有什么关系. 却也可以归结为最短路问题, 本文通过收集整理关于最短路径的普遍算法, 为研究最短路径问题在一些出行问题,工程问题,及实际生活问题中的应用,为企业和个人提供方便的选择方法. 二、最短路 最短路的定义对最短路问题的研究早在上个世纪60 年代以前就卓有成效了, 其中对赋权)0(? ijw 的有效算法是由荷兰著名计算机专家 在 1959 年首次提出的, 该算法能够解决两指定点间的最短路, 也可以求解图 G 中一特定点到其它各顶点的最短路. 后来海斯在 Dijkstr a 算法的基础之上提出了海斯算法. Ford 提出了 Ford 算法, 它能有效地解决含有负权的最短路问题. 但在现实生活中, 我们所遇到的问题大都不含负权, 所以我们在)0(? ijw 的情况下选择 Dijkstra 算法定义 1 若图),(EVGG?中各边 e 都赋有一个实数)(eW , 称为边 e 的权, 则称这种图为赋权图, 记为),,(WEVGG?. 定义2 若图),(EVGG?是赋权图且)(,0)(GEeeW??,若u是iv 到jv 的路)(uW 的权, 则称)(uW 为u 的长, 长最小的 iV 到jV 的路)(uW 称为最短路. 若要找出从 iv 到nv 的通路 u , 使全长最短,即???? min ij e u W u W e ???. 各类最短路算法的介绍 Floyd 算法 Floyd 算法又称为弗洛伊德算法, 插点法, 、 1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特· )],([ njiaA?开始, 递归地进行 n 次更新,即由矩阵 AD?)0( ,按一个公式,构造出矩阵)1(D ; 又用同样地公式由)1(D 构造出)2(D ; ……; 最后又用同样的公式由)1(D 构造出矩阵)(nD . 矩阵)(nD 的i 行j 列元素便是 i 号顶点到 j 号顶点的最短路径长度,称)(nD 为图的距离矩阵,同时还可引入一个后继节点矩阵 path 来记录两点间的最短路径. 下面介绍其算法过程: )1 从任意一条单边路径开始. 所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大; 安庆师范学院数学与计算数学学院