1、1目录目录 .1摘要 .2Abstract .3第一章 绪论 .41.1 课题背景 .41.2 目的意义 .51.3 国内外现状 .51.4 重点工作 .6第二章 最短路径问题的基础知识 .62.1 图的基本概念 .62.2 图的遍历 .82.2.1 深度优先搜索 .82.2.2 广度优先搜索 .9第三章 最短路径算法 .103.1 Dijkstra 算法 .103.1.1 算法原理 .103.1.2 算法描述 .103.1.3 算法步骤 .113.1.4 Dijkstra 算法的应用举例 .113.1.5 Dijkstra 算法的不足 .143.1.6 改进 Dijkstra 算法的基本思想
2、及实现 .143.2 bellman-ford 算法 .143.2.1 算法原理 .143.2.2 算法描述 .153.2.3 bellman-ford 算法的优缺点 .153.2.4 bellman-ford 算法的优化 .153.3 Floyd 算法 .163.3.1 算法原理 .163.3.2 算法描述 .163.3.3 Floyd 算法的优缺点 .172第四章 设计实现经典 Dijkstra 算法 .184.1 程序运行环境 .184.2 开发语言简介 .184.3 可行性分析 .204.4 需求分析 .204.5 软件结构 .214.6 模块详细设计与实现 .214.6.1 程序流程
3、图 .224.6.2 各模块设计 .224.7 系统特色 .254.8 系统需要改进的地方 .25第五章 结论 .265.1 最短路径算法 .265.2 心得与收获 .26致谢 .27参考文献 .283摘要随着社会的进步，科技的飞速发展，人们的办事效率也得到了极大的提高，在当今的社会里，花费最小的代价收获最大的效益，成为了当今社会里各行各业一直信奉的理念，这种理念最直接地体现在求最短路径的问题上，在生活中最常见的有通信问题、公交网络问题、旅游线路设计与优化中的运筹学问题等。解决这些问题的方法有很多种，但是针对不同的问题哪一种方法才是最优的呢?这就是在解决最短路径问题时首先要解决的问题。求最短路
4、径的方法有：dijkstra 算法、floyd 算法、bellman-ford 算法、SPFA 算法，如果我们能从这些算法中找出解决最短路径问题的最优方法，那么当人们再遇到这样的问题时，就可以节省很多人力物力，极大地提高了办事的效率。关键词：dijkstra 算法、floyd 算法、bellman-ford 算法、SPFA 算法4AbstractAlong with the progress of the society, the rapid development of science and technology, the efficiency of the people also get
5、 improved tremendously, in todays society, spend a minimum cost the benefit of the biggest gain, became todays 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
6、 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:
7、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 e
8、fficiency of the work.Keywords: dijkstra algorithm, Floyd algorithm, bellman-ford algorithm, SPFA algorithm .5第一章 绪论1.1 课题背景近年来，随着社会经济的飞速发展和人们生活水平的不断提高，汽车越来越成为人们不可或缺的交通工具。汽车数量的急剧增加使得城市道路交通日益复杂，而交通设施的建设远远落后于汽车数量的增加，因此交通堵塞现象十分严重，交通事故也愈发频繁。将最短路径算法应用于车辆导航系统，公交查询系统，将会提高行车效率，有效避免交通堵塞以及交通事故的发生，无疑是解决交通问题的利器
9、，也是智能交通的具体表现。随着城市经济的发展、规模的扩大以及人口的增长，城市交通问题日益突出。降低出行时间将使所有的国民产生效益，快速的交通、更好的信息及更好的市场可以提高城市的形象，能够带动经济增长。城市公共交通运输以其覆盖面广、经济、快捷的特点，成为绝大多数出行者的首选方式，也是各地城市政府大力发展的一种交通方式。本地市民特别是外来旅游、出差、就医等就急需了解本地道路情况，从而选择一个最优路线。1.2 目的意义我国城市道路的发展处于一个落后的水平,广大驾驶者可以获得信息的方式很少, 道路长期堵塞。道路实时信息的完整性和准确性得不到保证, 而且还没有专门的机构负责信息的发布和管理。本文通过对
10、几种最短路径算法的研究，比较找到适合城市道路路线选择的算法，用于改善城市的交通。1.3 国内外现状近年来，离散数学经过飞速发展，已成为我们研究中不可缺少的一部分，而它的一个分支图形学与计算机紧密地结合在一起，更成为广大学者的研究对象，逐渐的独立成章，越加的成熟起来。图的分类很细,也很广泛,大方向可分为有向图和无向图,而计算机中常用的树也是一种特殊的图。图的表示方法:邻接矩阵,完全关联矩阵,三元组都可以直接在计算机中表示.特殊的图有欧拉图和6哈密尔顿图。最短路径问题是图论中的一个典范问题，它已经被应用于众多领域.最短路径问题最直接的应用当数在地理信息领域，如：GIS 网络分析、城市规划、电子导航
11、等. 在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.1.4 重点工作由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些经典的算法.近些年来，对最短路径研究的热度依然不减，并且时间复杂度降得越来越低.所以在本论文中我将分析比较我们学习过的一些经典的最短路径算法，我还将提出一些改进这些算法的思路.最后还会设计实现经典的Dijkstra 算法的程序 .7第二章 最短路径问题的基础知识2.1 图的基本概念V1V2V3V4V5图 1图：图是一种较线形表和树更为复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间
12、都可能相关。在图中数据元素通常叫做顶点.说明：在保持图的点边关系不变的情况下，图形的位置、大小、形状都是无关紧要的.图 1 就是一个典型的图。弧： 两个顶点之间关系的集合 VR, VR,表示从 v 到 w 的一条弧。称v 为弧尾，w 为弧头。若 为一条有向弧，则称该图为有向图；若（v,w）为无向弧，此时的图称为无向图。完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。在有向图中，如果任意两项顶点之间都存在方向互为相反的两条弧，则称该图为由向完全图。稀疏图、稠密图：由很少边的图称为稀疏图。反之，成为稠密图。稀疏和稠密本身是模糊的概念，稀疏和稠密常常是相对而言的。邻接点：对于
13、无向图 G=（V，E） ，如果边（v,w） E,则称顶点 v 和 w 互为邻接点。度：以顶点 v 为头的弧的数目称为 v 的入度，以顶点 v 为尾的弧的数目称8为 v 的出度，出度和入度统称为度。路径：无向图 G=（V，E）中从顶点 v 到顶点 w 的路径是一个顶点序列其中 E，1 j m 。如果 G 是有向图，则路,.,10wmiii ),(1jijiv径也是有向的，路经的长度是路径上的边数或弧的数目，第一个顶点和最后一个顶点相同的路径称之为回路或环。简单路径：序列中顶点不重复出现的路径称为简单路径。除了第一个和最后一个顶点之外，其余顶点不重复出现的回路，称之为简单回路或简单环。图连通： 在
14、无向图 G 中，如果从顶点 v 到顶点 w 有路径，则称顶点 v 到顶点 w 是连通的。对于任意两个顶点都是连通的，则称图 G 是连通图。在有向图G 中，对于每一对顶点 E 都存在，则称 G 是强连通图。),(1jijiv邻接表：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中结点表示依附于顶点 的边。每个结点有 3 个域组iv成，其中邻接点域指示与顶点 邻接的点在图中的位置，链域指示下一条边或iv弧的结点；数据域存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了没有链域指向链表中第一个结点之外，还没有存储顶点的名或其他有关信息
15、的数据域。如下图 2 所示：表结点 头结点图 22.2 图的遍历从图中的某一顶点出发，按某种搜索方法访遍其余顶点，且使每一顶点仅被访问一次，这一过程称为图的遍历。通过图的遍历，我们可以得到图的很多信息，图的遍历是图算法领域的核心。图的常用遍历方法有两种：深度优先搜索（DFS）和广度优先搜索（BFS） 。2.2.1 深度优先搜索深度优先搜索如同它的名称所暗示的那样，这种搜索算法所遵循的搜素策略是尽可能“深”地搜索一个图，深度优先搜索类似树的先序遍历。data firstarcadjvex nextarc info9算法思想：对于图 G=（V，E） ，首先访问指定的起始顶点 S，然后访问与 S邻接
16、且未被访问的任一顶点 W1,再访问与 W1 邻接且未被访问的任一顶点W2， 重复上述过程。当不能再继续向下访问时，退回到上一个最近被访问的顶点，若它还有邻接顶点未被访问过。则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。算法 图的深度优先搜索算法void DFSTraverse(Graph G) for(i=0;iG.vexnum;i+)visitedi=0; / 初始化每个结点的访问标记for(i=0;iG.vexnum;i+)if(visitedi=0)DFS(G,i); / 选用 DFS_AL 或 DFS_M2.2.2 广度优先搜索广度优先搜索是一种分层的查找过程。它类似于
17、二叉树的层序遍历。每向前走一步可能访问一批项点，它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。算法思想:对于图 G=(V,E)，首先访问起始顶点 V，再依次访问 V 的各个未访问过的邻接顶点 W1，W2， ，Wi ，然后再依次访问 W1，W2，Wi 的所有未被访问过的邻接顶点，依次类推，直到图中所有顶点都被访问过为止。算法 图的广度优先搜索算法void DFSTraverse(Graph G) for(i=0;iG.vexnum;i+)visitedi=0; / 访问标记数组初始化for(i=0;iG.vexnum;i+)if( ! vi
18、sitedi )BFS(G,i); / Vi 未访问过。从 Vi 开始 BFS 搜索10第三章 最短路径算法3.1 Dijkstra 算法由荷兰计算机科学家艾兹赫尔戴克斯特拉（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。该算法的输入包含了一个有权重的有向图 G，以及 G 中的一个来源顶点S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径
19、相连。我们以 E 所有边的集合，而边的权重则由权重函数 w: E 0, 定义。因此，w(u, v) 就是从顶点 u到顶点 v 的非负花费值（cost） 。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有 V 中有顶点s 及 t， Dijkstra 算法可以找到 s 到 t 的最低花费路径(例如，最短路径) 。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。3.1.1 算法原理Dijkstra 算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用 Dijkstra 求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质3.1.2 算法描述这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作的。初始时，原点 s 的路径长度值被赋为 0 （ds = 0），若存在能直接到达的边（s,m），则把 dm设为 w（s,m）,同时把所有其他（ s 不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路
