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

1、目录目录1摘要2Abstract3第一章绪论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 算法的基本思想及实现143.2 bellman-ford算法143.2.1算法原理143.2.2算法描述153.2.3 b

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

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

4、tra算法、floyd算法、bellman-ford算法、SPFA算法AbstractAlong with the progress of the society, the rapid development of science and 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

5、 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

6、 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

7、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课题背

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

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

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

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

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

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

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

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

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

17、STraverse(Graph G) for(i=0;i<G.vexnum;i+) visitedi=0; / 访问标记数组初始化 for(i=0;i<G.vexnum;i+) if( ! visitedi ) BFS(G,i); / Vi未访问过。从Vi开始BFS搜索第三章 最短路径算法3.1 Dijkstra算法由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。

18、该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 所有边的集合，而边的权重则由权重函数 w: E  0, 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负花费值（cost）。边的花费可以想像成两个顶点之间的

19、距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花费路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。3.1.1 算法原理Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改

20、变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质3.1.2 算法描述这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径长度值被赋为 0 （ds = 0），若存在能直接到达的边（s,m），则把dm设为w（s,m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 

21、s 和上述 m 外 dv = ）。当算法结束时，dv 中储存的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 u 的路径。这条路径的长度是 du + w(u, v)。如果这个值比目前已知的 dv 的值要小，我

22、们可以用新值来替代当前 dv 中的值。拓展边的操作一直执行到所有的 dv 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 du 达到它最终的值的时候每条边（u, v）都只被拓展一次。算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 dv 的值已经是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 du 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边 (u, v) 进行拓展。3.1.3算法步骤1.

23、 初使时令 S=V0,T=其余顶点，T中顶点对应的距离值若存在<V0,Vi>，d(Vi)为<V0,Vi>弧上的权值 若不存在<V0,Vi>，d(Vi)为2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值 4. 重复上述步骤2、3，直到S中包含所有顶点，即S=T为止3.1.4 Dijkstra算法的应用举例以具体实例说明Dijkstra 算法的具体应用.例1. 利用Dijkstra 算法求图3 中节点A 到其它各节点的最优路径.GK 20 2

24、.9 3.2D 18N 4.4 3.5 3.2 4.5B 16HE Y 4.1 2.2 PL 14 4.2 2 3.4 4.5AI 12 5.6 2.9 3 4.22.2 OMC 10 3.4JF 3.5 4 2.2 3 8 0 2 4 6 X 8 图3 10 12 14相应的权值为： 根据Dijkstra 算法的实现步骤其计算过程可归纳为表1 所示.从表1 中可以看出从 到 的最短路径为 且到的距离为=18.3 在求到最短路径的过程中到其余各点的最短路径也相应求出.若以计算一次为计算单位，则利用Dijkstra算法计算 到 最短路径时所需的计算次数= 15+14+13+ +2 = 119次表

25、1采用Dijkstra 算法求解A到其他各节点最优路径的过程序号ABCDEFGHIJKLMNOP1-4.23.42-4.23.4/A9.06.93-4.2/A-4-/C11.910.95-8.58.3/B-10.311.210.96-8.6/B-11.510.311.210.97-11.510.3/D11.210.913.513.78-11.5-11.210.9/F13.513.713.19-11.5-11.2/E-13.513.713.110-11.5/D-13.513.713.111-13.513.713.1/J16.112-13.5/H13.7-18.

26、016.113-13.7/H-15.916.114-15.9/L16.118.715-16.1/M Dijkstra算法的不足算法的运行时间是 O(n2)，在现行电子地图中，网络模型的规模常常较大，节点数多达上千或上万，并且对网络模型的查询也要求实时性，因此Dijkstra 算法虽然在理论上是可行的，但在实际应用中不尽人意，当网络模型中节点数和边数较多的情况下，算法的计算量较大时间花费较多效率非常低。3.1.6 改进Dijkstra 算法的基本思想及实现表1 中的数值大多数是，都是无用运算，如果节点数量很大，将极其浪费运算时间.由于，节点是否在上次已经被计算出最短路

27、径未知，当前节点是否与节点是否相连也未知，也就是 未知，这时是已知的，故本次计算的 到底是不是，取决于上一步数值和的数值，从表达式可以看出，只要这两个数值不都是，本次计算的 就不会是，所以在上面Dijkstra 算法的实现步骤第(2) 步时，先判断一下，只要原来的， 的数值中至少有一个不是，才进行下面的计算，这样就保证了当预见 是时，不对它进行计算，避免了大量无效的计算，提高了搜索效率。3.2 bellman-ford算法是由 Richard Bellman 和 Lester Ford 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，

28、因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。3.2.1算法原理它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。松弛：每次松弛操作实际上是对相邻节点的访问，第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过条边，所以可知贝尔曼-福特算法所得为最短路径。负边权操作：与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。负权环判定：因为负权环可以无限制的降低总花费，所以如果

29、发现第n次操作仍可降低花销，就一定存在负权环。3.2.2算法描述对有向图G(V,E) ，用贝尔曼-福特算法求以Vs为源点的最短路径的过程：1. 建立dist ，表示目前已知源点到各个节点的最短距离，起始值dists=0 ，其余皆为。2. 建立Pred ，Pred 表示某节点路径上的父节点，起始值皆为NULL。3. 对(Vi,Vj)E ，比较distVi+(Vi,Vj) 和distVj ,并将小的赋给distVj ，如果修改了distV_j则PredVj= Vi（松弛操作）4. 重复以上操作V-1 次5. 再重复操作2一次，如distVj>distVi+(Vi,Vj) ,则此图存在负权环3

30、.2.3 bellman-ford算法的优缺点其优于Dijkstra算法的方面是边的权值可以为负数、实现简单。但缺点是时间复杂度过高，高达O(V E)。由此算法优化得到了多种单源最短路径问题的高效算法，如取队列优化而得的SPFA算法。3.2.4 bellman-ford算法的优化在实际操作中，贝尔曼-福特算法经常会在未达到V-1次前就出解，V-1其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。基于Bellman-Ford算法，提出SPFA(Shortest Path Faster Algorithm)算法，它是Bellman-Ford算法的一种队

31、列实现，减少了不必要的冗余计算。SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。 SLF 可使速度提高 15 20%；SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最

32、坏情况的出现，通常使用效率更加稳定的Dijkstra算法。3.3 Floyd算法Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。3.3.1 算法原理Floyd-Warshall算法的原理是动态规划。设Di,j,k为从i到j的只以(1k)集合中的节点为中间节点的最短路径的长度。1.若最短路径经过点k，则Di,j,k=Di,j,k-1+ Di,j,k-1。2.若最短路径不经过点k，则Di,j,k=Di,j,k-1。因此，Di,j,k=min(Di,j,k-1+ Di,j,k-1, Di,j,k-1)。在实际算法中，为了节约空间，可以直接在原来空间上进行迭

33、代，这样空间可降至二维。3.3.2算法描述Floyd算法的描述如下：for k 1 to n do for i 1 to n do for j 1 to n do if (Di,k+ Dk,j< Di,j) then Di,jDi,k+ Dk,j;其中Di,j表示由点i到点j的代价，当Di,j为 表示两点之间没有任何连接。3.3.3 Floyd算法的优缺点Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。 优点：容

34、易理解，可以算出任意两个节点之间的最短距离，代码编写简单 缺点：时间复杂度比较高，不适合计算大量数据。第四章 设计实现经典Dijkstra算法城市交通是一个城市的命脉。它是城市社会和经济活动的重要组成部分。伴随着国民经济和城市建设的快速发展，城市经济的繁荣，人口的增加，城市必须解决好人们出行的需求。城市交通直接关系着城市的经济发展和居民生活，对城市经济具有全局性、先导性的影响。但是随着城市的发展，道路交通越来越复杂人们很难得到最佳出行路线，这样给一些人的出行就带来了不便。因此，急需一个方便、快捷的最短路径算法，本文通过对最短路径算法的研究，编写了一个基于Dijkstra算法的程序。4.1程序运

35、行环境1. 操作系统要求：windows xp/windows 20002. 需要的软件： Visual Studio C+6.03. 计算机硬件要求：800MHZ奔腾 获其他处理器，256以上的内存4.2开发语言简介1VisualC+简介VisualC+是微软开发的一个集成环境，是使用C+的一个平台。它是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。Visual C+6.0不仅是一个C+编译器，而且是一个基于Windows操作系统的可视化集成开发环境（Int

36、egrated Development Environment,IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。2. MFC基础类类MFC,微软基础类(Microsoft Foundation Classes)，同VCL类似，是一种Application Framework，随微软Visual C+ 开发工具发布。该类库提供一组通用的可重用的类库供开发人员使用。大部分类均从CObject 直接或间接派生，只有少部分类例外

37、。MFC 应用程序的总体结构通常由 由开发人员从MFC类派生的几个类和一个CWinApp类对象（应用程序对象）组成。MFC 提供了MFC AppWizard 自动生成框架。Windows 应用程序中，MFC 的主包含文件为"Afxwin.h"。MFC,微软基础类(Microsoft Foundation Classes),实际上是微软提供的,用于在C+环境下编写应用程序的一个框架和引擎,VC+是WinDOS下开发人员使用的专业C+ SDK(SDK,Standard SoftWare Develop Kit,专业软件开发平台),MFC就是挂在它之上的一个辅助软件开发包，是对W

38、indowsAPI的封装，大约有100多个类，但常用的有二三十种。现在介绍一下MFC中比较重要也较常用的类。CWnd：窗口类，它是大多数“看得见的东西”的父类，比如视图CView、框架窗口CFrameWnd、工具条CToolBar、对话框CDialog、按钮CButton等。 CDocument文档，负责内存数据与磁盘的交互。最重要的是OnOpenDocument(读入),OnSaveDocument（写盘）,Serialize（读写） Cview：视图类，负责内存数据与用户的交互。包括数据的显示、用户操作的响应(如菜单的选取、鼠标的响应）。最重要的是OnDraw(重画窗口)，通常用CWnd:

39、Invalidate()来启动它。另外，它通过消息映射表处理菜单、工具条、快捷键和其他用户消息。 CDC：设备文本类。无论是显示器还是打印机，都是画图给用户看。这图就抽象为CDC类来完成。 Cdialog：对话框类。它是所有对话框的类。CwinApp：应用程序类。似于C中的main函数，是程序执行的入口和管理者，负责程序建立、消灭，主窗口和文档模板的建立。CGdiObject及子类,用于向设备文本画图。它们都需要在使用前选进DC。 Cbrush：刷子，填充 Cfont：字体，控制文字输出的字体 。Cfile：文件。最重要的不外是Open（打开）,Read（读入）,Write（写） Cstrin

40、g：字符串。封装了C中的字符数组，非常实用。 4.3 可行性分析可行性分析（Feasibility Analysis）也称为可行性研究，是在系统调查的基础上，针对新系统的开发是否具备必要性和可能性，对新系统的开发从技术、经济、社会的方面进行分析和研究，以避免投资失误，保证新系统的开发成功。可行性研究的目的就是用最小的代价在尽可能短的时间内确定问题是否能够解决。本系统对机器本身没有太高的要求，一般普通电脑完全可满足要求。对于软件技术要求，现在基于VisualC+ MFC架构的程序设计语言已非常成熟，从刚开始的C，到现在的MFC,C#的百花齐放，再到微软最新推出不久ASP.NET使用其中任何一门语

41、言开发都可以满足要求。可利用现有的电脑，装上VisualC+ 6.0软件，即可成编写该系统，对自己无经济的负担，在经济上完全可行。本系统开发不会侵犯他人、集体或国家利益，不存在侵权等问题，不违反国家法律,因此具有法律可行性。综上所述，技术上、经济上、法律上都是可行的,而且要求不高，所以该系统的开发是可行的。4.4需求分析需求分析简单地说就是分析用户的需求。需求分析的任务是通过详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统（手工系统或计算机系统）工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。现在城市发展越来越快，交通网络也越来越复杂，人们出行会有很多条路线选择

42、，怎么样选择才能找出最短路径？是人们目前迫切的需要。 4.5 软件结构本系统的软件结构比较简单，主要有三大部分组成：地图导入模块，导航模块和信息查询。如图4所示： 出行导航系统地图导入模块信息查询导航模块图4 软件结构4.6 模块详细设计与实现在前面的软件结构中，已将软件划分为多个模块，并将它们按照一定的原则组装起来，同时确定了每个功能及模块之间的外部接口。现在所要做的就是确定每个模块具体执行过程，也可以说是“过程设计”。在处理过程设计时我采用的是结构化程序设计（简称SP）方法。需要指出的是系统的详细设计并不是指具体的编程序，而是将概要设计阶段产生的系统功能模块图细化成很容易产生程序的图纸。因

43、此详细设计的结果基本决定了最终程序的质量。为软件的质量，延长软件的生存期，软件的可测试性、可维护性提供重要的保障。详细设计阶段的根本目标是确定应该怎样具体的实现所要求的系统，也就是说，经过这个阶段的设计工作，应该得出目标系统的精确描述，从而在编码阶段可以把这个描述直接翻译成用某种程序设计语言书写的程序。详细设计的目标不仅仅是逻辑上正确地实现每个模块的功能，更重要的是设计的处理过程应该尽可能简明易懂。4.6.1 程序流程图程序流程图又称为程序框图，它是历史悠久使用最广泛的描述软件设计的方法。1.下面是程序的流程图。开始导入地图Y导航N选择地点显示路线Y是否退出N结束图5程序流程图4.6.2 各模

44、块设计这个应用软件落实到具体的实现上时，首先要进行界面的设计，界面的功能布局是否合理、美观与否都关乎到这个软件质量。所以软件的界面也是很重要的一部分。这部分都做完以后剩下的就是编程了，这是所有预想功能能否实现的关键所在，也是设计难点。下面具体介绍各部分是怎么实现的。设计开始首先要建立一个基于对话框的MFC工程类，这样系统会默认生成一个基本的对话框架。里面包含确定和取消两个按钮，我们根据自己的需要进行增删。这个查询系统的主要模块有三个，一个是地图导入模块，第二个是导航模块，另一个是信息查询模块。这三个模块我做到了一起，这样比较方便用户操作。具体几面如下图所示。地图导入模块地图导入模块包含一个打开

45、文件对话框,对话框里面有选择地图文件，也就是说可以选择不同的地图打开。具体界面如下图所示。导航模块 信息查询模块信息结查询果显示导航结果显示（红色线条显示）4.7系统特色本系统根据出行人实际需求和需要进行设计和开发。 该系统功能基本上满足人们日常出行的需求。本次毕业设计的课题是基于最短路径研究的基础上开发的系统,可实现最短路径转乘查询功能。在具体实现本次设计时，采用C+编程语言，采用MFC类具有很好的图形化界面，操作简单，使用方便。系统的设计充分考虑了使用人员、用户的使用习惯，操作简单，方便灵活。4.8 系统需要改进的地方这是我首次用C+语言结合微软MFC类进行完整系统的开发，一切都是从零开始学习，所以开发的时候难免会过于简单，考虑的也不是很周到。同时由于时间仓促，有些功能的实现不是很完美。系统在设计过程中不可避免地遇到了各种各样的问题，由于整个系统完全都是由个人设计的，有关MFC类许多细节问题都要靠自己去摸索，加之本