城市道路最短路径算法研究论文

`

目录

目录 .............................................................................................................. 1 摘要 .............................................................................................................. 2 Abstract ......................................................................................................... 3 第一章

绪论 ............................................................................................... 4 1.1课题背景 ........................................................................................... 4 1.2目的意义 ........................................................................................... 5 1.3国外现状 ........................................................................................... 5 1.4重点工作 ........................................................................................... 6 第二章 最短路径问题的基础知识 ................................................................... 6

2.1 图的基本概念 ................................................................................... 6 2.2图的遍历 .......................................................................................... 8

2.2.1深度优先搜索 .......................................................................... 8 2.2.2广度优先搜索 ......................................................................... 9

第三章 最短路径算法 .................................................................................... 9

3.1 Dijkstra算法...................................................................................... 9

3.1.1 算法原理 ............................................................................... 10 3.1.2 算法描述 .............................................................................. 10 3.1.3算法步骤 ................................................................................ 11 3.1.4 Dijkstra算法的应用举例 ....................................................... 11 3.1.5 Dijkstra算法的不足 ............................................................. 13 3.1.6 改进Dijkstra 算法的基本思想及实现 ................................... 13 3.2 bellman-ford算法 ........................................................................... 14

3.2.1算法原理 ............................................................................... 14 3.2.2算法描述 .............................................................................. 14 3.2.3 bellman-ford算法的优缺点 ................................................. 15 3.2.4 bellman-ford算法的优化 .................................................... 15 3.3 Floyd算法 ................................................................................... 15

3.3.1 算法原理 .............................................................................. 15 3.3.2算法描述 .............................................................................. 16 3.3.3 Floyd算法的优缺点 ........................................................... 16

第四章 设计实现经典Dijkstra算法 .............................................................. 17

Word文档

`

4.1程序运行环境 .................................................................................. 17 4.2开发语言简介 ................................................................................. 17 4.3 可行性分析 .................................................................................... 19 4.4需求分析 ........................................................................................ 20 4.5 软件结构 ....................................................................................... 20 4.6 模块详细设计与实现 .................................................................... 20

4.6.1 程序流程图 ........................................................................... 21 4.6.2 各模块设计 .......................................................................... 22 4.7系统特色 ........................................................................................ 24 4.8 系统需要改进的地方 ...................................................................... 24 第五章 结论 ................................................................................................ 25

5.1 最短路径算法 ............................................................................... 25 5.2 心得与收获 .................................................................................. 25 致 ............................................................................................................... 26 参考文献 ..................................................................................................... 27

摘要

Word文档

`

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

关键词：dijkstra算法、floyd算法、bellman-ford算法、SPFA算法

Abstract

Along with the progress of the society, the rapid development of science and

Word文档

`

technology, the efficiency of the people also get improved tremendously, in today's society, spend a minimum cost the benefit of the biggest gain, became today's society in all walks of life have been believe in the idea, the idea is most directly reflected in for the shortest path problem, in the life the most common are communication problems, bus network problems, tourist line design and optimization of operations research, etc. To solve these problems a variety of ways, but according to the different 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 problem solving the optimal method, so when people again encountered this kind of problem, can save a lot of manpower and material resources to greatly improve the efficiency of the work.

Keywords: dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA

algorithm .

第一章 绪论

1.1课题背景

近年来，随着社会经济的飞速发展和人们生活水平的不断提高，汽车越来越

Word文档

`

成为人们不可或缺的交通工具。汽车数量的急剧增加使得城市道路交通日益复杂，而交通设施的建设远远落后于汽车数量的增加，因此交通堵塞现象十分严重，交通事故也愈发频繁。将最短路径算法应用于车辆导航系统，公交查询系统，将会提高行车效率，有效避免交通堵塞以及交通事故的发生，无疑是解决交通问题的利器，也是智能交通的具体表现。

随着城市经济的发展、规模的扩大以及人口的增长，城市交通问题日益突出。降低出行时间将使所有的国民产生效益，快速的交通、更好的信息及更好的市场可以提高城市的形象，能够带动经济增长。城市公共交通运输以其覆盖面广、经济、快捷的特点，成为绝大多数出行者的首选方式，也是各地城市政府大力发展的一种交通方式。本地市民特别是外来旅游、出差、就医等就急需了解本地道路情况，从而选择一个最优路线。

1.2目的意义

我国城市道路的发展处于一个落后的水平,广大驾驶者可以获得信息的方式很少,道路长期堵塞。道路实时信息的完整性和准确性得不到保证,而且还没有专门的机构负责信息的发布和管理。

本文通过对几种最短路径算法的研究，比较找到适合城市道路路线选择的算法，用于改善城市的交通。

1.3国外现状

近年来，离散数学经过飞速发展，已成为我们研究中不可缺少的一部分，而它的一个分支图形学与计算机紧密地结合在一起，更成为广大学者的研究对象，逐渐的独立成章，越加的成熟起来。图的分类很细,也很广泛,大方向可分为有向图和无向图,而计算机中常用的树也是一种特殊的图。图的表示方法:邻接矩阵,完全关联矩阵,三元组都可以直接在计算机中表示.特殊的图有欧拉图和哈密尔顿图。

最短路径问题是图论中的一个典问题，它已经被应用于众多领域.最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等.在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.

Word文档