最短路径算法分类与应用研究

《最短路径算法分类与应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课题结题论文题目最短路径算法分类与应用研究学院专业班级学生姓名指导教师2008年10月12最短路径算法分类与应用研究姓名:班级:指导教师:摘要本文研究目的在于收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。通过应用最短路径算法中的蚁群算法来解决浙江旅行商问题，以各城市经纬度作为初始条件，通过MATL

2、AB程序计算最短路径，并画出最短路线图。关键词最短路径算法，最短路径应用，蚁群算法，浙江旅行商12目录摘要I关键词I第一章绪论2第二章最短路径算法2一、Dijkstra算法21、适用条件和范围22、算法描述23、算法实现2二、A*算法21、适用条件和范围32、算法原理33、算法描述3三、Bellman-Ford算法31、适用条件和范围32、算法描述43、算法实现4四、Topological Sort(拓扑排序)算法41、适用条件和范围42、算法描述43、算法实现4五、SSSP On DAG算法41、适

3、用条件和范围42、算法描述53、算法实现5六、Floyd算法51、适用范围52、算法描述53、算法小结5七、Prim算法51、适用范围52、算法描述53、算法实现5八、Kruskal算法61、适用范围62、算法描述63、算法实现6九、Johnson算法61、适用范围62、算法实现6第三章最短路径算法应用6一、TSP问题的介绍6二、TSP问题算法的介绍61、贪心算法62、模拟退火算法73、遗传序列算法74、蚁群算法8三、算法应用81、解决浙江旅行商问题时算法描述82、蚁群算法的MATLAB程序描述93、

4、蚁群算法解决浙江旅行商问题11第四章总结12致谢12参考文献1312第一章绪论随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题—即已知起始结点，求最短路径的问题；确定终点的最短路径问题—与确定

5、起点的问题相反，该问题是已知终结结点，求最短路径的问题；在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；确定起点终点的最短路径问题—即已知起点和终点，求两结点之间的最短路径；全局最短路径问题—求图中所有的最短路径。用于解决最短路径问题的算法被称作最短路径算法。本文研究目的在于收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解

6、题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。第二章最短路径算法本课题旨在总结归纳最短路径的普遍算法，经收集资料发现最短路径算法主要有：Dijkstra算法、A*算法、Bellman-Ford算法、Topological Sort(拓扑排序)算法、SSSP On DAG算法、Floyd算法、Prim算法、Kruskal算法及Johnson算法。其中最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法及Floyd算法。一、Dijkstra算法1、

7、适用条件和范围：（1）单源最短路径（从源点s到其它所有顶点v）；（2）有向图和无向图（无向图可以看作，同属于边集E的有向图）；（3）所有边权非负（任取都有）。2、算法描述：如果v1→v2→v3→v4是v1→v4的最短路径，则v1→v2→v3一定是v1→v3的最短路径。v2→v3→v4一定是v2→v4的最短路径。3、算法实现：（1）初始化：dis[v]=maxint；dis[s]=0；pre[s]=s;S={s}；（2）For i:=1 to n①取V-S中的一顶点u使得dis[u]=min{dis[v

8、]

9、v∈V-S}②S=S+{u}③For V-S中每个顶点v do Relax（3）算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点。程序见参考文献[8]。二、A*算法1、适用条件和范围：12A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数F，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象，以便使