最短路径算法的研究毕业设计

1、 本科毕业设计(论文)题目名称： 最短路径算法的研究 学 院： 计算机科学技术 专业年级： 计算机科学与技术（师范）08级 学生姓名： 王超奇 班级学号： 2班13 号 指导教师： 刘锡祥 二一二 年 六月 八日摘 要本文目的在于研究关于最短路径的算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为其他的同学提供一些解题的思路与方法，为他们提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。通过应用最短路径算法中的蚁群算法来解决浙江旅行商问题，以各城市经纬度作为初始条件，通过matlab程序计算最短路径，并画出最短路线图

2、。关键词：最短路径算法；最短路径应用；蚁群算法；浙江旅行商iabstractin this paper, the purpose is to collect the shortest path algorithm about common for the shortest path problem in some travel problems, management, engineering problems and practical application of life, for enterprise and individual with convenient selection m

3、ethod. at the same time, the students for the mathematical modeling provide some ideas and methods for problem solving, provide favorable resources for the game. at last, by use of ant colony algorithm to solve the zhejiang traveling salesman problem. through the application of the shortest path alg

4、orithm of ant colony algorithm to solve the zhejiang traveling salesman problem in the city as the coordinates of initial conditions, through the matlab calculation shortest paths, and draw the shortest route mapkey words：the shortest path algorithm, the shortest path application, ant colony algorit

5、hm, zhejiang traveling salesmaii目 录摘 要iabstractii第1章绪论11.1 选题的意义及目的11.1.1 选题的意义11.1.2 选题的目的11.2 选题经过及国内外动态11.2.1 选题经过11.2.2 选题的国内外动态2第2章最短路径算法的介绍32.1dijkstra 算法32.1.1 算法介绍及适用条件和范围32.1.2 算法描述和算法实现32.1.3 具体算法分析42.2 a* 算法82.2.1 算法介绍及适用条件和范围82.2.2 算法描述和算法实现92.2.3 具体算法分析92.3 bellman-ford 算法112.3.1 算法介绍及适

6、用条件和范围112.3.2 算法描述和算法实现112.3.3 具体算法设计122.4 topological sort 算法152.4.1 算法介绍及适用条件和范围152.4.2 算法描述和算法实现162.4.3 具体算法设计162.5 sssp on dag 算法202.5.1 算法介绍及适用条件和范围202.5.2 算法描述和算法实现212.6 floyd 算法212.6.1 算法介绍及适用条件和范围212.6.2 算法描述和算法实现212.6.3 算法具体分析22第3章 最短路径算法的比较26第4章 最短路径算法的应用284.1 tsp问题的介绍284.2 tsp问题算法的介绍284.2

7、.1 贪心算法284.2.2 模拟退火算法294.2.3 遗传序列算法294.2.4 蚁群算法304.3 算法应用314.3.1 解决浙江旅行商问题时算法描述314.3.2 蚁群算法的算法描述314.3.3 蚁群算法解决浙江旅行商问题34第5章 最短路径算法的展望36绪 论38致 谢39参考文献40ii第1章 绪论1.1 选题的意义及目的1.1.1 选题的意义随着计算机科学的发展，人们生产生活经济利润的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。最短路径问题是图论

8、研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题即已知起始结点，求最短路径的问题；确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径；全局最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称作最短路径算法。1.1.2 选题的目的本文研究目的在于收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管

9、理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。1.2 选题经过及国内外动态1.2.1 选题经过二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域，如地理信息领域等。现实生活中最短路径的运用非常多，算法也很多，最短路径的分析是网络分析最基本的功能之一，近年来，随着网络的不断发展，网络中的最短路径问题具有重大的理论意义和应用价值。1.2.2 选题的国内外动态最短路径这一重要问题早在20世纪

10、初就已经得到人们的高度重视，当时也有很多科学家研究这一问题的求解方法。但直到1959年荷兰计算机科学家edsger wybe dijkstra才给出这一问题求解的基本方思想，并给出了算法。当时的dijkstra提出这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题，后来这个算法就成了众所周知的dijkstra算法，也成了一代经典。 现如今比较流行的最短路径规划算法主要有以下三类：第一类是基于图论理论的算法；第二类则是基于传统人工智能理论的算法；第三类则是基于智能控制技术的算法。特别是近10年来，智能控制技术在路径规划问题中得到广泛应用，人们的研究兴趣也逐渐从对前两类的算法改进转到了

11、对第三类算法的进一步研究。第2章 最短路径算法的介绍2.1 dijkstra 算法2.1.1 算法介绍及适用条件和范围1.算法介绍dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用open, close表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。2.适用条件和范

12、围（1）单源最短路径（从源点s到其它所有顶点v）；（2）有向图和无向图（无向图可以看作，同属于边集e的有向图）；（3）所有边权非负（任取都有）。2.1.2 算法描述和算法实现1.算法描述如果 v1 v2 v3 v4 是 v1 v4 的最短路径，则 v1 v2 v3 一定是 v1 v3 的最短路径。 v2 v3 v4 一定是 v2 v4 的最短路径。2.算法实现（1）初始化：disv=maxint ；diss=0；pres=s;s=s；（2）fori:=1ton取v-s中的一顶点u使得disu=mindisv|vv-ss=s+uforv-s中每个顶点vdorelax （3）算法结束：disi为s

13、到i的最短距离；prei为i的前驱节点。程序见参考文献8。2.1.3 具体算法分析下图中的有向图，应用dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。125341050100201030 60#include using namespace std; const int maxnum = 100; const int maxint = 999999; / 各数组都从下标1开始 int distmaxnum; / 表示当前点到源点的最短路径长度 int prevmaxnum; / 记录当前点的前一个结点 int cmaxnummaxnum; / 记录图的两点间路径长度 i

14、nt n, line; / 图的结点数和路径数 / n - n nodes / v - the source node / dist - the distance from the ith node to the source node / prev - the previous node of the ith node / c - every two nodes distance void dijkstra(int n, int v, int *dist, int *prev, int cmaxnummaxnum) bool smaxnum; / 判断是否已存入该点到s集合中 for(int

15、 i=1; i=n; +i) disti = cvi; si = 0; / 初始都未用过该点 if(disti = maxint) previ = 0; else previ = v; distv = 0; sv = 1; / 依次将未放入s集合的结点中，取dist最小值的结点，放入结合s中 / 一旦s包含了所有v中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 / 注意是从第二个节点开始，第一个为源点 for(int i=2; i=n; +i) int tmp = maxint; int u = v; / 找出当前未使用的点j的distj最小值 for(int j=1; j=n

16、; +j) if(!sj) & distjtmp) u = j; / u保存当前邻接点中距离最小的点的号码 tmp = distj; su = 1; / 表示u点已存入s集合中 / 更新dist for(int j=1; j=n; +j) if(!sj) & cujmaxint) int newdist = distu + cuj; if(newdist =1; -i) if(i != 1) cout quei ; else cout quei n; / 输入路径数 cin line; int p, q, len; / 输入p, q两点及其路径长度 / 初始化c为maxint for(int

17、i=1; i=n; +i) for(int j=1; j=n; +j) cij = maxint; for(int i=1; i p q len; if(len cpq) / 有重边 cpq = len; / p指向q cqp = len; / q指向p，这样表示无向图 for(int i=1; i=n; +i) disti = maxint; for(int i=1; i=n; +i) for(int j=1; j=n; +j) printf(%8d, cij); printf(n); dijkstra(n, 1, dist, prev, c); / 最短路径长度 cout 源点到最后一个顶

18、点的最短路径长度: distn endl; / 路径 cout 源点到最后一个顶点的路径为: ; searchpath(prev, 1, n); 输入数据: 5 7 1 2 10 1 4 30 1 5 100 2 3 50 3 5 10 4 3 20 4 5 60 输出数据: 999999 10 999999 30 100 10 999999 50 999999 999999 999999 50 999999 20 10 30 999999 20 999999 60 100 999999 10 60 9999992.2 a* 算法2.2.1 算法介绍及适用条件和范围1.算法介绍a*（a-sta

19、r）算法是一种静态路网中求解最短路径最有效的方法；公式表示为： f(n)=g(n)+h(n), 其中f(n) 是从初始点经由节点n到目标点的估价函数， g(n) 是在状态空间中从初始节点到n节点的实际代价， h(n)是从n到目标节点最佳路径的估计代价2.适用条件和范围a*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数f，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小f值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向进行。因此，a*算法只要求产生问题的全部状态空间的部分结点，就

20、可以求解问题了，搜索效率较高。确定估价函数方法通常是：搜索到该结点的深度+ 距离目标最近的程度。3.使用原理如图有如下的状态空间：（起始位置是a，目标位置是p，字母后的数字表示节点的估价值）状态空间图搜索过程中设置两个表：open和closed。open表保存了所有已生成而未考察的节点，closed表中记录已访问过的节点。算法中有一步是根据估价函数重排open表。这样循环中的每一步只考虑open表中状态最好的节点。2.2.2 算法描述和算法实现算法描述及其实现（1）初始状态： open=a5;closed=;（2）估算a5，取得搜有子节点，并放入open表中；open=b4, c4, d6;

21、closed=a5（3）估算b4，取得搜有子节点，并放入open表中；open=c4, e5, f5, d6; closed=b4, a5（4）估算c4；取得搜有子节点，并放入open表中；open=h3, g4, e5, f5, d6;closed=c4, b4, a5（5）估算h3，取得搜有子节点，并放入open表中；open=o2, p3, g4, e5, f5, d6; closed=h3c4, b4, a5（6）估算o2，取得搜有子节点，并放入open表中；open=p3, g4, e5, f5, d6; closed=o2, h3, c4, b4, a5（7）估算p3，已得到解。2

22、.2.3 具体算法分析在国际象棋的棋盘上，一匹马共有8个可能的跳跃方向，求从起点到目标点之间的最少跳跃次数。#include #include usingnamespacestd;structknightintx,y,step;intg,h,f;booloperatork.f;k;boolvisited88;/已访问标记(关闭列表)intx1,y1,x2,y2,ans;/起点(x1,y1),终点(x2,y2),最少移动次数ansintdirs82=-2,-1,-2,1,2,-1,2,1,-1,-2,-1,2,1,-2,1,2;/8个移动方向priority_queueque;/最小优先级队列(

23、开启列表)boolin(constknight&a)/判断knight是否在棋盘内if(a.x0|a.y=8|a.y=8)returnfalse;returntrue;intheuristic(constknight&a)/manhattan估价函数return(abs(a.x-x2)+abs(a.y-y2)*10;voidastar()/a*算法knightt,s;while(!que.empty()t=que.top(),que.pop(),visitedt.xt.y=true;if(t.x=x2&t.y=y2)ans=t.step;break;for(inti=0;i8;i+)s.x=t

24、.x+dirsi0,s.y=t.y+dirsi1;if(in(s)&!visiteds.xs.y)s.g=t.g+23;/23表示根号5乘以10再取其ceils.h=heuristic(s);s.f=s.g+s.h;s.step=t.step+1;que.push(s);intmain()charline5;while(gets(line)x1=line0-a,y1=line1-1,x2=line3-a,y2=line4-1;memset(visited,false,sizeof(visited);k.x=x1,k.y=y1,k.g=k.step=0,k.h=heuristic(k),k.f=

25、k.g+k.h;while(!que.empty()que.pop();que.push(k);astar();printf(togetfrom%c%cto%c%ctakes%dknightmoves.n,line0,line1,line3,line4,ans);return0;2.3 bellman-ford 算法2.3.1 算法介绍及适用条件和范围1.算法介绍bellman-ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 g=（v,e），其源点为s，加权函数 w是 边集 e 的映射。对图g运行bellman-ford算法的结果是一个布尔值

26、，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图g的任意顶点v的最短路径dv。2.适用条件和范围（1）单源最短路径(从源点s到其它所有顶点v)；（2）有向图和无向图(无向图可以看作(u,v),(v,u)同属于边集e的有向图)；（3）边权可正可负(如有负权回路输出错误提示)；（4）差分约束系统2.3.2 算法描述和算法实现1.算法描述1,.初始化：将除源点外的所有顶点的最短距离估计值 dv +, ds 0; 2.迭代求解：反复对边集e中的每条边进行松弛操作，使得顶点集v中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次） 3.检验负权

27、回路：判断边集e中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dv中。2.算法实现（1）pasca语言 for i:=1 to |v|-1 do for 每条边(u,v)e do relax(u,v,w); for每条边(u,v)e do if disu+w 0 & distk edgekj+distj 更新当前值 2.3.3 具体算法设计typedef struct oo int len,num; struct oo *next; link;typedef struct int num;

28、 link *next; graph;/* node图的邻接表 n节点总数 s源点 dis到源点的最短路径长度 pre最短路径上的前驱结点 算法返回true，当且仅当途中不包含从源点可达的负权回路*/bool bellmanford(graph node,int n,int s) int dismax,premax; int i,j; link *p; for(i=0;in;i+) disi=maxvalue; prei=-1; diss=0; for(i=0;ilen+disinum) disp-num=p-len+disi;prep-num=i; p=p-next; p=nodei.nex

29、t; while(p) if(p-len+disinum) return false; p=p-next; for(i=0;in;i+) printf(%d %dn,i,disi); j=i; while(j!=-1) printf(%d ,j); j=prej; coutendl; return true;/这个是邻接矩阵const int max = 100;const int maxvalue = 1000;int graphmaxmax,n;/* graph图的邻接阵 n 图的节点数 s 源点 dis 存放最短路径 pre 存放最短路径上的前驱节点 算法返回true，当且仅当途中不包含

30、从源点可达的负权回路，并输出每个节点最短路径的前驱值*/bool bellmanford(int graphmax,int n,int s) int dismax,premax; int i,j,k; for(i=0;in;i+) disi=maxvalue; prei=-1; diss=0; for(i=0;in;i+) for(j=0;jdisi+graphij) disj=disi+graphij; prej=i; for(j=0;jdisi+graphij) return false; for(i=0;in;i+) printf(%d %dn,i,disi); k=i; while(p

31、rek!=-1) printf(%d ,prek); k=prek; cout0)do顶点v出栈；输出v；计数器增1；for与v邻接的顶点udoa.dec(indgru)；b.ifindgru=0then顶点u入栈；（6）exit(i=|v|)。2.4.3 具体算法设计#define maxv 30#define ok 1#define error 0typedef char vertextype;typedef int status;typedef struct arcnode int adjvex; struct arcnode *nextarc;arcnode;typedef struc

32、t vnode vertextype data; arcnode *firstarc;vnode,adjlistmaxv ;typedef struct adjlist vertices; int vexnum,arcnum;algraph;int locatevex(algraph g,char m);status creat_graph1(algraph &g);int dfs_topsort(algraph g,int n);/拓扑排序算法void dfs(algraph g,int v,int&flag);/深度优先搜索void menuselect();头文件#include#inc

33、lude#include#include#includehead.hint visitedmaxv;int finishedmaxv;int dfs_topsort(algraph g,int n) int flag=1,i; for(i=0;in;i+) /置初值 visitedi=0; finishedi=1; i=0; /从编号为0的顶点开始遍历 while(flag&iadjvex=0) dfs(g,p-adjvex,flag); finishedp-adjvex =1; p=p-nextarc ; int locatevex(algraph g,char m) int i; for(

34、i=0;ig.vexnum;i+) if(g.verticesi.data=m)return i; return error;status creat_graph1(algraph &g) int i,j,r;char m,n;arcnode *p; printf(请输入顶点数：); scanf(%d,&g.vexnum); printf(请输入边数：); scanf(%d,&g.arcnum); printf(请输入图的所有顶点：); for(i=0;ig.verticesi.data;g.verticesi.firstarc=null; printf(请输入图的所有边，如a-b边记为ab，

35、：n); for(r=0;rm;cinn; i=locatevex(g,m);j=locatevex(g,n); p=(arcnode*)malloc(sizeof(arcnode); p-adjvex=j; p-nextarc=g.verticesi.firstarc; g.verticesi.firstarc=p; return ok; void menuselect() int done=1,select,i; algraph g; printf(please input select number); while(done) printf(请输入操作码：); scanf(%d,&sel

36、ect); switch(select) case 1: if(creat_graph1(g)printf(ok); printf(nn); break; case 2: dfs_topsort( g,g.vexnum); printf(nn); break; case 3: done=0; break; default:printf(输入的操作码错误nn); 实现文件#include#include#include#include#includehead.hvoid main() printf(图的拓扑排序); menuselect(); 2.5 sssp on dag 算法2.5.1 算法

37、介绍及适用条件和范围适用条件和范围（1）dag(directedacyclicgraph,有向无环图)；（2）边权可正可负。2.5.2 算法描述和算法实现1.算法描述（1）toposort；（2）iftoposort=falsethenhalt(notadag)；（3）for拓扑序的每个顶点udoforu的每个邻接点vdorelax(u,v,w)；（4）算法结束后：如有环则输出错误信息；否则disi为s到i的最短距离，prei为前驱顶点。2.算法实现此算法时间复杂度o(v+e)，时间和编程复杂度低，如遇到符合条件的题目(dag)，推荐使用。还有，此算法的步骤（3）可以在toposort中实现，

38、这样即减小了此算法复杂度的一个系数。2.6 floyd 算法2.6.1 算法介绍及适用条件和范围1.算法介绍通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵a=a(i,j) nn开始，递归地进行n次更新，即由矩阵d(0)=a，按一个公式，构造出阵d(1)；又用同样地公式由d(1)构造出d(2)；最后又用同样的公式由d(n-1)构造出矩阵d(n)。矩阵d(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称d(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。2.适用条件和范围（1）apsp(allpairsshortestpaths)

39、；（2）稠密图效果最佳；（3）边权可正可负。2.6.2 算法描述和算法实现算法描述（1）初始化：disu,v=wu,v。（2）fork=1tonfori=1tonforj=1tonifdisi,jdisi,k+disk,jthendisi,j=disi,k+disk,j。（3）算法结束：dis即为所有点对的最短路径矩阵。2.6.3 算法具体分析以无向图g为入口，得出任意两点之间的路径长度lengthij，路径pathijkjava 算法途中无连接得点距离用0表示，点自身也用0表示 public class floyd int length = null;/ 任意两点之间路径长度 int path = null;/