最短路径毕业论文.doc

--------------------------校验:_____________-----------------------日期:_____________最短路径毕业论文最短路算法的比较与应用作者:胡义棚指导老师:丁超摘要:本文较详尽地介绍了最短路算法相关的基本概念,给出了Dijkstra算法、Floyd算法、SPFA算法等常用算法及其核心思想,并对各种最短算法做了多角度的比较,阐述了各种算法的应用范围,并对其在运输网络、舰船通道路线设计、工业生产中的应用做出了举例说明,侧重于模型的建立、思考和证明的过程,:最短路算法Dijkstra算法Floyd算法SPFA算法一、引言最短路算法是图论中的核心问题之一,他是许多更深层次算法的基础,同时,,本文通过收集整理关于最短路径的普遍算法,为研究最短路径问题在一些出行问题,工程问题,及实际生活问题中的应用,、最短路对最短路问题的研究早在上个世纪60年代以前就卓有成效了,,,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法定义1若图中各边e都赋有一个实数,称为边的权,则称这种图为赋权图,,若u是到的路的权,则称为的长,,使全长最短,,插点法,、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·,递归地进行n次更新,即由矩阵,按一个公式,构造出矩阵;又用同样地公式由构造出;……;,称为图的距离矩阵,:,如果两点之间没有边相连,则权为无穷大;对于每一对顶点和,;把图用邻接距阵表示出来,如果从到有路可达,则,表示该路的长度;否则为无穷大;定义一个距阵用来记录所插入点的信息,表示从到需要经过的点,初始化;把各个顶点插入图中,比较插点后的距离与原来的距离,,,如果的值变小,则;在中包含有两点之间最短道路的信息,(迪杰斯特拉)算法是典型的单源最短路径算法,,,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,**********下面介绍其算法过程:首先,引进一个辅助向量,:若从到有弧,则为弧上的权值;否则置为∞.显然,,下一条长度次短的最短路径是哪一条呢?假设该次短路径的终点是,则可想而知,这条路径或者是,,,假设为已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为)或者是弧,,下一条长度次短的最短路径的长度必是其中,或者是弧上的权值,:1),,,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为,