论文格式 - 副本2new

PAGE92011年秋季学期《图论》课程论文姓名：潘玉军学院：理学院学号：1001014243年级：2010级专业：数学与应用数学班级：2班图论中最短路算法及其应用潘玉军（佳木斯大学理学院数学系,黑龙江佳木斯154007）摘要：随着旅行人数的增加以及节约时间的需要，图论中的最短路算法显得越来越重要，在实际的旅行中，对几个地点的遍历中，人们总是希望能找到一个最短最有效的路径可以遍历所有的景点，在一个大的景点内部同样如此。本文运用了图论中的最短路径算法，邻接矩阵，赋权图等知识，针对我校暨佳木斯大学内的几处标志性建筑的遍历为基础，建模了赋权图，模拟了在任意两点之间的最短路径的实现以及编程显示。关键词：图论；最短路径；Dijkstra算法；计算路径和一：需求分析本论文主要实现查询我校任意两点之间的最短路径，以我校方位布局为根据，首先要对我校的布局有所了解，然后估计出主要建筑物的距离。数学建模，运用图论知识进行解决。此方法可用于多数别的地方，如景点的查询，旅行路线的查询等。实际应用非常广泛。二：运用图论基本知识在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:ER为从边到实型权值的映射。路径P=(v0,v1,……,vk)的权是指其组成边的所有权值之和：定义u到v间最短路径的权为从结点u到结点v的最短路径定义为权的任何路径。[1]边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被用来表示时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。单目标最短路径问题：找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。单对结点间的最短路径问题：对于某给定结点u和v，找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决。对于该问题的最坏情况，从渐进意义上看，目前还未发现比最好的单源算法更快的方法。每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。在某些单源最短路问题中，可能存在权为负的边。如果图G(V,E)不包含由源s可达的负权回路，则对所有，最短路径的权的定义依然正确[1]。即使它是一个负值也是如此。但如果存在一从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的结点不存在最短路径——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径，因此如果从s到v的某路径中存在一负权回路，我们定义。图1含有负权和负权回路的图图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s到该结点的最短路径的权。因为从s到a只存在一条路径(路径<s,a>)，所以：。类似地，从s到b也只有一条通路，所以：。[1]从s到c则存在无数条路径：<s,c>,<s,c,d,c>,<s,c,d,c,c,d,c>等等。因为回路<c,d,c>的权为6+(-3)=3>0，所以从s到c的最短路径为<s,c>，其权为：。类似地，从s到d的最短路径为<s,c,d>，其权为：。[2]同样，从s到e存在无数条路径：<s,e>,<s,e,f,e>,<s,e,f,e,f,e>等等.由于回路<e,f,e>的权为3+(-6)=-3<0，所以从s到e没有最短路径。只要穿越负权回路任意次，我们就可以发现从s到e的路径可以有任意小的负权值，所以：类似地，[2]因为g是从f可达的结点，我们从s到g的路径可以有任意小的负权值，则：。结点h，j，i也形成一权值为负的回路，但因为它们从s不可达，因此。[2]一些最短路径的算法，例如Dijkstra算法，都假定输入图中所有边的权取非负数，如公路地图实例。另外一些最短路算法，如Bellman-Ford算法，允许输入图中存在权为负的边，只要不存在从源点可达的权为负的回路，这些算法都能给出正确的解答[3]。特定地说，如果存在这样一个权为负的回路，这些算法可以检测出这种回路的存在。三：数学建模本论文着手解决实例为我校情况，主要抽象出了以下八个典型的地点：大学东门，理学院，U型楼，图书馆，主楼，新食堂，机械院，材料院。以下为我校平面图：大学东门大学东门图书馆主楼新食堂机械院材料理院U型楼60100120705060208040605030图2我校主要建筑分布图运用图论知识对上图进行邻接矩阵的表示，为了表示方便我对上图的地点：大学东门，理学院，U型楼，图书馆，主楼，新食堂，机械院，材料院。分别由数字1，2，3，4，5，6，7，8代表。123456781∞50∞6070∞∞∞250∞120∞40∞∞∞3∞120∞∞∞60∞∞460∞∞∞20∞80∞57040∞20∞5060∞6∞∞60∞50∞100∞7∞∞∞8060100∞308∞∞∞∞∞∞30∞表1：我校建筑抽象图的加权邻接表示表四：算法分析及实现本文运用了Dijkstra算法，其抽象算法为：ProcedureDijkstra(G:所有权都为证书的加权连通图)｛G带有顶点a=v０,v1,...,vn=z和权w（vi,vj）,若｛vi,vj｝不是G中的边，则w(vi,vj)=∞｝Fori:=1tonL(vi):=∞L(a):=0S:=¢{初始化标记，a的标记为0，其余结点标记为∞，S是空集}Whilez不属于SBeginU:=不属于S的L(u)最小的一个顶点S：=S∪｛u｝For所有不属于S的顶点vIfL(u)+w(u,v)<L(v)ThenL(v):=L(u)+w(u,v){这样就给S中添加带最小标记的顶点并且更新不再S中的顶点的标记}End{L(z)=从a到z的最短路的长度}[4]以上为运用Dijkstra算法描述，此算法给出了一个大致的步骤的步骤。也可称其为伪码表述，运用此算法可以实现求取两结点之间的最短路径，运用c语言实现Dijkstra算法为：VoidShortestPath_Floyd(AdjMatrixg,WeightTypedist[MAX_VERTEX_NUM][MAX_VERTEX_NUM],VertexSetpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM]){ inti,j,k; for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) { dist[i][j]=g.arcs[i][j]; InitList(&path[i][j]); if(dist[i][j]<INF) { AddTail(&path[i][j],g.vertex[i].name); AddTail(&path[i][j],g.vertex[j].name); } } for(k=0;k<g.vexnum;k++) for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) { if(dist[i][k]+dist[k][j]<dist[i][j]) { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=JoinList(path[i][k],path[k][j]); } }}[5][6]五：运行结果以及分析基于以上核心算法加上运用对二维数组以及链表的操作完成了此功能，本程序是运行于dos显示没有运用mfc界面编程，掌握了一些基础知识以后，基本可以完成本实验。本设计中只是完成了要求的内容，并没有考虑算法的时间复杂度，然而这些也是图论所介绍过的，在大程序中就显得的非常重要了，但是本例考虑程序小为了实现方便没有予以考虑，特别是在显示任意两节点的所有可行的方法上，对于五个结点的计算复杂度达到了o（n*n*n*n*n）的程度，这在以后的编程中需要注意的。六：总结经过此次的图论的课程报告，使我对于图论，特别是图论中的最短路径算法有了深刻的了解，也使我对于编程的能力有所提高。图论是生活技巧的一门学问，里面很多经典算法。把理论运用于实践能得到意想不到的乐趣，感觉这也是做学问的真是内涵所在。同时我也认识到了自己的不足，对于理论知识学习的不扎实，还需要借助工具书课本，对于编程也需要参考才能最后自己实现，可见，学海无涯，需要学习的东西还有很多。感谢李东老师的指导教学，在以后的日子里我会更加努力的学习，不仅学习理论，还有把理论运用于实践之中。参考文献：[1]蒋长浩，吴建专，顾国华，殷翔《图论及其应用》，东南大学出版社，2002年。[2]徐俊明，《图论及其应用》，中国科学与技术大学出版社，2000年。[3]殷剑宏、吴开亚主编，《图论及其算法》，中国科学技术大学出版社，2005年。GraphtheoryanditsapplicationinthemostshortcircuitalgorithmJerrypanAbstract:Withtheincreaseinthenumberofpeopletravelingandsavethetimeofneed,graphtheoryofthemostshortcircuitalgorithmismoreandmoreimportantintheactualtrip,toseveralsitesofthetraverse,peoplealwayswanttofindtheshortestoneofthemosteffectivepathcantraverseallthesites,inabigattractionsinternalaswell.Thispaperusedagraphoftheshortestpathalgorithm,adjacencymatrix,andempowermentchartandsoonknowledge,inviewofourschoolandinseveraloftheuniversityofjiamusithelandmarkbuildingtraverseasthefoundation,