《最短路径算法分类与应用研究》由会员分享，可在线阅读，更多相关《最短路径算法分类与应用研究（15页珍藏版）》请在金锄头文库上搜索。
1、课题结题论文题 目最短路径算法分类与应用研究学 院专 业班 级学生指导教师2008年10月最短路径算法分类与应用研究姓 名:班 级:指导教师 :摘要本文研究目的在于收集整理关于最短路径的普遍算法， 为研究最短路径问题在一些出行问题、 管理问题、 工程问题及实际生活问题中的应用， 为企业和个人提供方便的选择方法。 同时， 也为参加数学建模的同学提供一些解题的思路与方法， 为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。通过应用最短路径算法中的蚁群算法来解决浙江旅行商问题， 以各城市经纬度作为初始条件，通过MATLAB 程序计算最短路径，并画出最短路线图。关键词最短路径算法，最短路径应
2、用，蚁群算法，浙江旅行商摘要I关键词I第一章绪论1第二章最短路径算法1一、Dijkstra 算法 11、适用条件和范围 12、算法描述13、算法实现1二、A*算法11、适用条件和范围 12、算法原理23、算法描述2三、Bellman-Ford 算法21、适用条件和范围 22、算法描述23、算法实现3四、Topological Sort（拓扑排序）算法31、适用条件和范围 32、算法描述33、算法实现3五、SSSP On DAGi：法31、适用条件和范围 32、算法描述43、算法实现4六、Floyd算法41、适用范围42、算法描述43、算法小结4七、Prim算法41、适用范围42、算法描述43、
3、算法实现4八、Kruskal 算法51、适用范围52、算法描述53、算法实现5九、Johnson 算法51、适用范围52、算法实现5第三章最短路径算法应用5一、TSP问题的介绍5二、TSP问题算法的介绍51、贪心算法52、模拟退火算法63、遗传序列算法 64、蚁群算法7三、算法应用71、解决浙江旅行商问题时算法描述 72、蚁群算法的 MATLABi序描述 83、蚁群算法解决浙江旅行商问题 10第四章总结11致谢11参考文献12第一章 绪论随着电脑科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为电脑科学、运筹学、 地理信息科学等学科的一个研究热点。 也正因为最短路径问题在实际生产生活
4、中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图由结点和路径组成的中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题即已知起始结点，求最短路径的问题；确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转确实定起点的问题；确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径；全局最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称作最短路径算法。本文研究目的在于收集整理关于最
5、短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。第二章 最短路径算法本课题旨在总结归纳最短路径的普遍算法，经收集资料发现最短路径算法主要有： Dijkstra 算法、A*算法、Bellman-Ford 算法、Topological Sort（拓扑排序）算法、SSSP On DA既法、 Floyd 算法 、 Prim 算法、 Kruskal 算法及 Johnson 算法。其中最常用的路径算法有： Dijks
6、tra 算法、A*算法、Bellman-Ford算法及Floyd算法。一、 Dijkstra 算法1、适用条件和范围： 1 单源最短路径从源点 s 到其它所有顶点 v ；2有向图和无向图无向图可以看作u,v ， v,u 同属于边集E 的有向图 ；3所有边权非负任取i, j E 都有Wij0 。2、算法描述：如果 v1- v2f v3f v4是 v1- v4的最短路径，则 v1- v2f v3 一定是 v1f v3的 最短路径。v2f v3f v4 -一定是 v2f v4的最短路径。3、算法实现： 1 初始化： disv=maxint v V,v s ； diss=0 ； pres=s;S=s
7、； 2 For i:=1 to n取 V-S 中的一顶点 u 使得 disu=mindisv|v 6 V-S S=S+uFor V-S 中每个顶点 v do Relaxu,v,WU,v 3 算法结束： disi 为 s 到 i 的最短距离； prei 为 i 的前驱节点。程序见参考文献8 。二、A*算法1、适用条件和范围：A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索，但不同的是每生成一 个子结点需要计算估价函数 F,以估算起始结点到该结点的代价及它到达目标结点的代价的和； 每当扩展结点时，总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向
8、进行。因此，A*算法只要求产生问题的全部状态空间的部分结点，就可以求解问题了，搜索效率较 高。确定估价函数方法通常是：搜索到该结点的深度+距离目标最近的程度。2、算法原理：如图有如下的状态空间：起始位置是A,目标位置是P,字母后的数字表示节点的估价值状态空间图搜索过程中设置两个表：OPEW口 CLOSED OPE破保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPENB1中状态最好的节点。3、算法描述：1初始状态：OPEN=A5;CLOSED电2估算A5,取得搜有子节点，并放入OPEN1中；OPEN=B4,
9、 C4, D6; CLOSED=A53估算B4,取得搜有子节点，并放入OPEN1中；OPEN=C4, E5, F5, D6; CLOSED=B4, A54估算C4;取得搜有子节点，并放入OPEN1中；OPEN=H3, G4, E5, F5, D6;CLOSED=C4, B4, A55估算H3,取得搜有子节点，并放入OPEN1中；OPEN=O2, P3, G4, E5, F5, D6; CLOSED=H3c4, B4, A56估算O2,取得搜有子节点，并放入OPEN1中；OPEN=P3, G4, E5, F5, D6; CLOSED=O2, H3, C4, B4, A57估算P3,已得到解。三、
10、Bellman-Ford 算法1、适用条件和范围：1单源最短路径（从源点s到其它所有顶点V）;2有向图和无向图（无向图可以看作（u,v）,（v,u）同属于边集E的有向图）；3边权可正可负（如有负权回路输出错误提示 ）；4差分约束系统。2、算法描述： 1 对每条边进行|V| 次 Relax 操作；2如果存在u,vC E使得disu+wdisv,则存在负权回路；否则 disv即为s到v 的最短距离， prev 为前驱。3、算法实现：1PASCAL言For i:=1 to |V|-1 doFor 每条边(u,v) C E doRelax(u,v,w);For 每条边(u,v) C E doIf di
11、su+w 0 & distk edgekj+distj更新当前值 四、 Topological Sort（ 拓扑排序 ） 算法1、适用条件和范围：1AOVO （ActivityOn Vertex Network）; 2 有向图；3作为某些算法的预处理过程（如 DP）。2、算法描述： 1 每次挑选入度为 0 的顶点输出 （ 不计次序 ） ； 2 如果最后发现输出的顶点数小于|V| ，则说明有回路存在。3、算法实现： 1 数据结构： adj: 邻接表 ; 有 4 个域 u,v,w,next ； indgri: 顶点 i 的入度；stack: 栈；2初始化 :top=0 （栈顶指针 ） ； 3 将初
12、始状态所有入度为 0 的顶点压栈；4 I=0（计数器 ） ； 5 While 栈非空 （top0） do顶点v出栈；输出v;计数器增1;For与v邻接的顶点u doa. dec（indgru） ；b. If indgru=0 then 顶点 u 入栈； 6 EXIT（I=|V|） 。五、SSSP On DAGM法1、适用条件和范围： 1 DAG（Directed Acyclic Graph, 有向无环图 ） ； 2 边权可正可负。2、算法描述： 1 Toposort ； 2 If Toposort=False Then HALT(Not aDAG)； 3 For 拓扑序的每个顶点 u doFo
13、r u 的每个邻接点 v doRelax(u,v,w) ； 4 算法结束后：如有环则输出错误信息；否则 disi 为 s 到 i 的最短距离， prei 为前驱 顶点。3、算法实现：此算法时间复杂度O(V+E)， 时间和编程复杂度低， 如遇到符合条件的题目 (DAG)， 推荐使用。还有，此算法的步骤 3 可以在 toposort 中实现，这样即减小了此算法复杂度的一个系数。六、 Floyd 算法1、适用范围： 1 APSP(All Pairs Shortest Paths) ； 2 稠密图效果最正确； 3 边权可正可负。2、算法描述： 1 初始化： disu,v=wu,v 。 2 For k=1 to nFor i=1 to nFor j=1 to nIf disi,jdisi,k+disk,jThenDisi,j=disi,k+disk,j。 3算法结束：dis 即为所有点对的最短路径矩阵。3、算法小结：此算法简单有效， 由于三重循环结构紧凑， 对于稠密图， 效率要高于执行|V| 次 Dijkstra算法。4、算法实现：见参考文献11 。七、 Prim 算法1、适用范围： 1 用于求无向图的最小生成树； 2 无向图( 有向图的是最小树形图 ) ； 3 多用于稠密图。2、算法描述：设图 G = V ， E ，其生成树的顶点集合为 U。 1 把 v0 放入 U ；
