最短路径毕业论文.doc

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