城市道路最短路径算法研究毕业论文(1)

1、目录目录摘要3Abstract4第一章绪论51课题背景51.2目的意义51.3国内外现状514重点工作6第二章最短路径问题的基础知识72图的基本概念72.2图的遍历82.2.1深度优先搜索82.2.2广度优先搜索9第三章最短路径算法103Dijkstra 算法103.1.1算法原理103.1.2算法描述103.1.3算法步骤113.1.4 Dijkstra算法的应用举例113.1.5 Dijkstra 算法的不足143.1.6改进Dijkstra算法的基本思想及实现143.2 bellmanford 算法143.2.1算法原理143.2.2算法描述153.2.3 bellmarvford 算法

2、的优缺点153.2.4 bellmarvford 算法的优化153.3 Floyd 算法163.3.1算法原理163.3.2算法描述163.3.3 Floyd算法的优缺点17第四章 设计实现经典Dijkstra算法184程序运行环境184.2开发语言简介184.3可行性分析204.4需求分析204.5软件结构214.6模块详细设计与实现214.6.1程序流程图224.6.2各模块设计224.7系统特色254.8系统需要改进的地方25第五章结论265最短路径算法265.2心得与收获26致谢27参考文献28摘要随着社会的进步，科技的飞速发展，人们的办事效率也得到了极大的提高， 在当今的社会里，花费

3、最小的代价收获最大的效益，成为了当今社会里各行各业 一直信奉的理念，这种理念最直接地体现在求最短路径的问题上，在生活中最常 见的有通信问题、公交网络问题、旅游线路设计与优化中的运筹学问题等。解决 这些问题的方法有很多种，但是针对不同的问题哪一种方法才是最优的呢?这就 是在解决最短路径问题时首先要解决的问题。求最短路径的方法有：dijkstra算 法、floyd算法、bellman-ford算法、SPFA算法，如果我们能从这些算法中找出解 决最短路径问题的最优方法，那么当人们再遇到这样的问题时，就可以节省很多 人力物力，极大地提高了办事的效率。关键词：dijkstra算法、floyd算法、bel

4、lman-ford算法、SPFA算法AbstractAlong with the progress of the society, the rapid development of science and tech no logy, the efficie ncy of the people also get improved tremendously, i n todays society, spend a minimum cost the benefit of the biggest gain, became todays society in all walks of I讦e have

5、been believe in the idea, the idea is most directly reflected in for the shortest path problem, in the I讦e the most common are comm un icati on problems, bus network problems, tourist line desig n and optimization of operations research, etc. To solve these problems a variety of ways, but accordi ng

6、 to the d 讦 fere nt problem which method is the best? This is the shortest path problem solving the first to solve the problem. For the shortest path method is: dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA algorithm, if we can from these algorithms to find the shortest path prob

7、lem solving the optimal method, so when people again encountered this kind of problem, can save a lot of man power and material resources to greatly improve the efficiency of the work.Keywords： dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA algorithm .第一章绪论1.1课题背景近年来，随着社会经济的飞速发展和人

8、们生活水平的不断提高，汽车越来越 成为人们不可或缺的交通工具。汽车数量的急剧增加使得城市道路交通日益复 杂，而交通设施的建设远远落后于汽车数量的增加，因此交通堵塞现象十分严重, 交通事故也愈发频繁。将最短路径算法应用于车辆导航系统，公交查询系统，将 会提高行车效率，有效避免交通堵塞以及交通事故的发牛，无疑是解决交通问题 的利器，也是智能交通的具体表现。随着城市经济的发展、规模的扩大以及人口的增长，城市交通问题日益突出。 降低出行时间将使所有的国民产牛效益，快速的交通、更好的信息及更好的市场 可以提高城市的形象，能够带动经济增长。城市公共交通运输以其覆盖面广、经 济、快捷的特点，成为绝大多数出行

9、者的首选方式，也是各地城市政府大力发展 的一种交通方式。本地市民特别是外来旅游、出差、就医等就急需了解本地道路 情况，从而选择一个最优路线。1.2目的意义我国城市道路的发展处于一个落后的水平，广大驾驶者可以获得信息的方式 很少，道路长期堵塞。道路实时信息的完整性和准确性得不到保证,而且还没有专 门的机构负责信息的发布和管理。本文通过对几种最短路径算法的研究，比较找到适合城市道路路线选择的算 法，用于改善城市的交通。1.3国内外现状近年來，离散数学经过飞速发展，已成为我们研究中不可缺少的一部分，而 它的一个分支图形学与计算机紧密地结合在一起，更成为广大学者的研究对象， 逐渐的独立成章，越加的成熟

10、起来。图的分类很细，也很广泛，大方向可分为有向 图和无向图,而计算机中常用的树也是一种特殊的图。图的表示方法:邻接矩阵, 完全关联矩阵，三元组都可以直接在计算机中表示特殊的图有欧拉图和哈密尔 顿图。最短路径问题是图论中的一个典范问题，它已经被应用于众多领域.最短路 径问题最直接的应用当数在地理信息领域，女口： GIS网络分析、城市规划、电子 导航等在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短 路径问题的一个典型的例子.1.4重点工作由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生 了一些经典的算法.近些年来，对最短路径研究的热度依然不减，并且时间复杂 度降得

11、越来越低.所以在本论文中我将分析比较我们学习过的一些经典的最短路 径算法，我还将提出一些改进这些算法的思路.最后还会设计实现经典的Dijkstra 算法的程序.第二章 最短路径问题的基础知识2.1图的基本概念图1图：图是一种较线形表和树更为复杂的数据结构。在图形结构中，结点之间 的关系可以是任意的，图中任意两个数据元素之间都可能相关。在图中数据元素 通常叫做顶点说明：在保持图的点边关系不变的情况下，图形的位置、大小、 形状都是无关紧要的图1就是一个典型的图。弧：两个顶点之间关系的集合VR, g VR,表示从v到w的一条弧。称v 为弧尾，w为弧头。若为一条有向弧，则称该图为有向图； 若(v,w)

12、为无向弧，此时的图称为无向图。完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完 全图。在有向图中，如果任意两项顶点之间都存在方向互为相反的两条弧，则称 该图为由向完全图。稀疏图、稠密图：由很少边的图称为稀疏图。反之，成为稠密图。稀疏和稠 密木身是模糊的概念，稀疏和稠密常常是相对而言的。邻接点:对于无向图G二(V,E),如果边(v, w) g E,则称顶点v和w互为邻接点。度：以顶点v为头的弧的数目称为v的入度，以顶点v为尾的弧的数目称为V的出度，出度和入度统称为度。路径：无向图G二（V, E）中从顶点V到顶点W的路径是一个顶点序列 （u=Mo，M.忆加二）其中1 j m o如

13、果G是有向图，贝V路 径也是有向的，路经的长度是路径上的边数或弧的数冃，第一个顶点和最后一个 顶点相同的路径称之为回路或环。简单路径：序列中顶点不重复出现的路径称为简单路径。除了第一个和最后 一个顶点之外，其余顶点不重复出现的回路，称之为简单回路或简单环。图连通：在无向图G中，如果从顶点v到顶点w有路径，则称顶点v到顶 点w是连通的。对于任意两个顶点都是连通的，则称图G是连通图。在有向图G 中，对于每一对顶点（v,._pv.）gE都存在，则称G是强连通图。邻接表：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个 单链表，第i个单链表中结点表示依附于顶点匕的边。每个结点有3个域组成，

14、其中邻接点域指示与顶点匕邻接的点在图中的位置，链域指示下一条边或弧的结 点；数据域存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。 在表头结点中，除了没有链域指向链表中第一个结点之外，还没有存储顶点的名 或其他有关信息的数据域。如下图2所示：表结点头结点adjvexn exta rcinfodatafirstarc2.2图的遍历从图中的某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被 访问一次，这一过程称为图的遍历。通过图的遍历，我们可以得到图的很多信息, 图的遍历是图算法领域的核心。图的常用遍历方法有两种：深度优先搜索（DFS） 和广度优先搜索（BFS）o2.2.1深

15、度优先搜索深度优先搜索如同它的名称所暗示的那样，这种搜索算法所遵循的搜素策略 是尽可能“深”地搜索一个图，深度优先搜索类似树的先序遍历。算法思想：对于图G二(V, E),首先访问指定的起始顶点S,然后访问与S 邻接且未被访问的任一顶点W】,再访问与Wi邻接且未被访问的任一顶点W2, 重复上述过程。当不能再继续向下访问时，退回到上一个最近被访问的顶点，若 它还有邻接顶点未被访问过。则从该点开始继续上述搜索过程，直到图中所有顶 点均被访问过为止。算法图的深度优先搜索算法void DFSTraverse(Graph G) for(i=0;iG.vex nu m;i+)visitedi=O;/初始化每

16、个结点的访问标记for(i=0;iG.vex num;i+)讦(visitedi=O)DFS(G；/ 选用 DFS_AL 或 DFS_M2.2.2广度优先搜索广度优先搜索是一种分层的查找过程。它类似于二叉树的层序遍历。每向前 走一步可能访问一批项点，它不是一个递归的算法。为了实现逐层的访问，算法 必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。算法思想:对于图G=(V,E),首先访问起始顶点V,再依次访问V的各个未访 问过的邻接顶点Wi, W2, Wi,然后再依次访问Wi, W2,Wi的所有未被访问过的邻接顶点，依次类推，直到图中所有顶点都被访问过为止。算法图的广度优先搜索算法void

17、 DFSTraverse(Graph G) for(i=0;iG.vex nu m;i+)visitedi=O;/访问标记数组初始化for(i=0;idistVi+(Vi,Vj)，则此图存在负权环3.2.3 bellman-ford算法的优缺点其优于Dijkstra算法的方面是边的权值可以为负数、实现简单。但缺点是 时间复杂度过高，高达0(V E)o由此算法优化得到了多种单源最短路径问题的 高效算法，如取队列优化而得的SPFA算法。3.2.4 bellman-ford 算法的优化在实际操作中，贝尔曼福特算法经常会在未达到vi次前就出解，vi其实 是最大值。于是可以在循环中设置判定，在某次循环不

18、再进行松弛时，直接退出 循环，进行负权环判定。基于 Bellman-Ford 算法，提出 SPFA(Shortest Path Faster Algorithm)算法，它 是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。SPFA算法有 两个优化算法SLF和LLL： SLF： Small Label First策略，设要加入的节点是j, 队首元素为i,若dist(j)vdist(i),则将j插入队首，否则插入队尾。LLL： Large Label Last策略，设队首元素为i,队列中所有dist值的平均值为x,若dist(i)x则将i 插入到队尾，查找下一元素，直到找到某一

19、 i使得dist(i)v二x,则将i出对进行松弛 操作。SLF可使速度提高15 20%； SLF + LLL可提高约50%。在实际的应 用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率 更加稳定的Dijkstra算法。3.3 Floyd 算法Floyd算法乂称为弗洛伊徳算法，插点法，是一种用于寻找给定的加权图中 顶点间最短路径的算法。3.3.1算法原理Floyd-Warshall算法的原理是动态规划。设Djk为从i到j的只以(l.k)集合中的节点为中间节点的最短路径的长度。1. 若最短路径经过点k,则DiJ,k=DiJ,k-l+ Di,j,k-lo2. 若最短路径不经

20、过点k,则Dij,k=Dij,k-io 因此，Di,j,k=min(Di,j,ki+ Dij,k-i)o在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降 至二维。3.3.2算法描述Floyd算法的描述如下：for k 1 to n dofor i 1 to n dofor j 1 to n doif (Di,k+ Dkj 工具条 CToolBar 对话框 CDialog 按钮 CButton 等。 CDocument文档，负责内存数据与磁盘的交互。最重要的是0nOpenDocument （读 入）,OnSaveDocument （写盘）,Serialize （读写）Cvi

21、ew：视图类，负责内存数据与用户的交互。包括数据的显示、用户操作 的响应（如菜单的选取、鼠标的响应）。最重要的是0nDT3W（重画窗口），通常用 CWnd: Invalidate （）来启动它。另外,它通过消息映射表处理菜单、工具条、快 捷键和其他用户消息。CDC：设备文本类。无论是显示器还是打印机，都是画图给用户看。这图就 抽象为CDC类来完成。Cdialog：对话框类。它是所有对话框的类。CwinApp：应用程序类。似于0中的main函数，是程序执行的入口和管理者, 负责程序建立、消灭，主窗口和文档模板的建立。CGdiObject及子类，用于向设备文本画图。它们都需要在使用前选进DCoCb

22、rush：刷子，填充Cfont：字体，控制文字输出的字体。Cfile：文件。最重要的不外是Open （打开）,Read （读入）,Write （写）Cstring：字符串。封装了 C中的字符数组，非常实用。4.3可行性分析可行性分析（Feasib订ity Analysis）也称为可行性研究，是在系统调查 的基础上，针对新系统的开发是否具备必要性和可能性，对新系统的开发从技术、 经济、社会的方面进行分析和研究，以避免投资失误，保证新系统的开发成功。 可行性研究的目的就是用最小的代价在尽可能短的时间内确定问题是否能够解 决。本系统对机器本身没有太高的要求，一-般普通电脑完全可满足要求。对于软件技术

23、要求，现在基于VisualC+ MFC架构的程序设计语言己非常成 熟，从刚开始的0,到现在的MFC, C#的百花齐放，再到微软最新推出不久ASP. NET 使用其中任何一门语言开发都可以满足要求。可利用现有的电脑，装上VisualC+ 6.0软件，即可成编写该系统，对自己 无经济的负担，在经济上完全可行。本系统开发不会侵犯他人、集体或国家利益，不存在侵权等问题，不违反 国家法律，因此具有法律可行性。综上所述，技术上、经济上、法律上都是可行的，而且要求不高，所以该系 统的开发是可行的。4.4需求分析需求分析简单地说就是分析用户的需求。需求分析的任务是通过详细调查现 实世界要处理的对象（组织、部门

24、、企业等），充分了解原系统（手工系统或计 算机系统）工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。现在城市发展越来越快，交通网络也越來越复朵，人们出行会有很多条路线 选择，怎么样选择才能找出最短路径？是人们廿前迫切的需要。4.5软件结构本系统的软件结构比较简单，主要有三大部分组成：地图导入模块，导航模块和信息查询。如图4所示：图4软件结构4.6模块详细设计与实现在前面的软件结构中，已将软件划分为多个模块，并将它们按照一定的原则 组装起来，同时确定了每个功能及模块之间的外部接口。现在所要做的就是确定 每个模块具体执行过程，也可以说是“过程设计”。在处理过程设计时我采用的是结构化程

25、序设计（简称SP）方法。需要指岀 的是系统的详细设计并不是指具体的编程序，而是将概要设计阶段产生的系统功 能模块图细化成很容易产生程序的图纸。因此详细设计的结果基本决定了最终程 序的质量。为软件的质量，延长软件的生存期，软件的可测试性、可维护性提供 重要的保障。详细设计阶段的根本目标是确定应该怎样具体的实现所要求的系统，也就是 说，经过这个阶段的设计工作，应该得岀目标系统的精确描述，从而在编码阶段 可以把这个描述直接翻译成用某种程序设计语言书写的程序。详细设计的目标不 仅仅是逻辑上正确地实现每个模块的功能，更重要的是设计的处理过程应该尽可 能简明易懂。4.6.1程序流程图程序流程图乂称为程序框

26、图，它是历史悠久使用最广泛的描述软件设计的方 法。1 下而是程序的流程图。4.6.2各模块设计图5程疗:流程图这个应用软件落实到具体的实现上时，首先要进行界面的设计，界面的功能 布局是否合理、美观与否都关乎到这个软件质量。所以软件的界面也是很重要的 一部分。这部分都做完以后剩下的就是编程了，这是所有预想功能能否实现的关 键所在，也是设计难点。下而具体介绍各部分是怎么实现的。设计开始首先要建立一个基于对话框的MFC工程类，这样系统会默认生成 一个基本的对话框架。里面包含确定和取消两个按钮，我们根据自己的需要进行 增删。这个查询系统的主要模块有三个，一个是地图导入模块，第二个是导航模块，另一个是信

27、息查询模块。这三个模块我做到了一起，这样比较方便用户操作。 具体几而如下图所示。弘行人导航系统载入地S1数据Q）遶择路程点0）僧息査看帮助Qi）D etai X 尙 1*1地图导入模块地图导入模块包含一个打开文件对话框，对话框里面有选择地图文件，也就 是说可以选择不同的地图打开。具体界而如下图所示。导航模块诘输入起点和终点起点I武汉工业学院确定终点I汉口央车站取消信息査询模块信息结査询果显示XJ的前前点 询询询摄 杳香否耳 所所所相称号鬍 st 点点mllnelu武汉工业学侯1iwtrS00导航结果显示（红色线条显示）4.7系统特色本系统根据出行人实际需求和需要进行设计和开发。该系统功能基本上

28、满 足人们日常出行的需求。本次毕业设计的课题是基于最短路径研究的基础上开发的系统，可实现最短 路径转乘查询功能。在具体实现本次设计时，采用C+编程语言，采用MFC类具 有很好的图形化界面，操作简单，使用方便。系统的设计充分考虑了使用人员、 用户的使用习惯，操作简单，方便灵活。4.8系统需要改进的地方这是我首次用C+语言结合微软MFC类进行完整系统的开发，一切都是从 零开始学习，所以开发的时候难免会过于简单，考虑的也不是很周到。同时由于 时间仓促，有些功能的实现不是很完美。系统在设计过程中不可避免地遇到了各 种各样的问题，由于整个系统完全都是由个人设计的，有关MFC类许多细节问 题都要靠自己去摸

29、索，加之本人水平有限，并没有完全地理解MFC的强大功能, 而且还存在着许多不足之处。如：受开发条件和开发时间的限制，本系统只利用了本地数据读取，它同应用程 序处于同一系统中，能存储的数据量也有一定限制，并没有发挥出其数据库方面 的优势；在系统的界面设计上也不够精致，界面不够美观。有些地方看上去比较粗糙。第五章结论5.1最短路径算法寻找两点间的最短路径的算法很多，目前公认经典的算法是在1959年提出 的Dijkstra算法。它不仅可以求出从始点到终点的最短路径长度，而且也能算出 从始点到其它各定点的最短路径的长度。Dijkstra算法在网络点数很多的时候有其局限性：一是用矩阵来存弧段信息 的方法内存开销比较大；二是由于算法的复杂度是N的平方，当N很大时运算 速度很慢，甚至会让人难以忍受。针对上述局限性很多人提出了不少改进的算法, 主要体现在：针对稀疏图可以把矩阵表示改为邻接表来表示，以节省存储空间； 通过尝试各种排序和搜索方法，减少算法中的排序和搜索次数。5.2心得与收获本次毕业设计到此已经顺利结束，通过这次的毕业设计，我学到了很多。在 以前的三年半时间内我学习了很多的