城市道路最短路徑算法研究論文正文

1、目錄目錄1摘要2Abstract3第一章緒論41.1課題背景41.2目的意義51.3國內外現狀51.4重點工作6第二章 最短路徑問題的基礎知識62.1 圖的基本概念62.2圖的遍歷8深度優(yōu)先搜索8廣度優(yōu)先搜索9第三章 最短路徑算法103.1 Dijkstra算法103.1.1 算法原理103.1.2 算法描述10算法步驟113.1.4 Dijkstra算法的應用舉例113.1.5 Dijkstra算法的不足143.1.6 改進Dijkstra 算法的基本思想及實現143.2 bellman-ford算法14算法原理14算法描述153.2.3 bellman-ford算法的優(yōu)缺點153.2.4

2、bellman-ford算法的優(yōu)化153.3 Floyd算法163.3.1 算法原理16算法描述163.3.3 Floyd算法的優(yōu)缺點17第四章 設計實現經典Dijkstra算法184.1程序運行環(huán)境184.2開發(fā)語言簡介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摘要隨著社會的進步，科技的飛速發(fā)展，人們的辦事效率也得到了極大的提高，在當今的社會里，花費最小的代價收

3、獲最大的效益，成為了當今社會里各行各業(yè)一直信奉的理念，這種理念最直接地體現在求最短路徑的問題上，在生活中最常見的有通信問題、公交網絡問題、旅游線路設計與優(yōu)化中的運籌學問題等。解決這些問題的方法有很多種，但是針對不同的問題哪一種方法才是最優(yōu)的呢?這就是在解決最短路徑問題時首先要解決的問題。求最短路徑的方法有：dijkstra算法、floyd算法、bellman-ford算法、SPFA算法，如果我們能從這些算法中找出解決最短路徑問題的最優(yōu)方法，那么當人們再遇到這樣的問題時，就可以節(jié)省很多人力物力，極大地提高了辦事的效率。關鍵詞：dijkstra算法、floyd算法、bellman-ford算法、S

4、PFA算法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 all walks of life have been b

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

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

7、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課題背景近年來，隨著社會經濟的飛速發(fā)展和人們生活水平的不斷提高，汽

8、車越來越成為人們不可或缺的交通工具。汽車數量的急劇增加使得城市道路交通日益復雜，而交通設施的建設遠遠落后于汽車數量的增加，因此交通堵塞現象十分嚴重，交通事故也愈發(fā)頻繁。將最短路徑算法應用于車輛導航系統，公交查詢系統，將會提高行車效率，有效避免交通堵塞以及交通事故的發(fā)生，無疑是解決交通問題的利器，也是智能交通的具體表現。隨著城市經濟的發(fā)展、規(guī)模的擴大以及人口的增長，城市交通問題日益突出。降低出行時間將使所有的國民產生效益，快速的交通、更好的信息及更好的市場可以提高城市的形象，能夠帶動經濟增長。城市公共交通運輸以其覆蓋面廣、經濟、快捷的特點，成為絕大多數出行者的首選方式，也是各地城市政府大力發(fā)展的

9、一種交通方式。本地市民特別是外來旅游、出差、就醫(yī)等就急需了解本地道路情況，從而選擇一個最優(yōu)路線。1.2目的意義我國城市道路的發(fā)展處于一個落后的水平,廣大駕駛者可以獲得信息的方式很少,道路長期堵塞。道路實時信息的完整性和準確性得不到保證,而且還沒有專門的機構負責信息的發(fā)布和管理。本文通過對幾種最短路徑算法的研究，比較找到適合城市道路路線選擇的算法，用于改善城市的交通。1.3國內外現狀近年來，離散數學經過飛速發(fā)展，已成為我們研究中不可缺少的一部分，而它的一個分支圖形學與計算機緊密地結合在一起，更成為廣大學者的研究對象，逐漸的獨立成章，越加的成熟起來。圖的分類很細,也很廣泛,大方向可分為有向圖和無向

10、圖,而計算機中常用的樹也是一種特殊的圖。圖的表示方法:鄰接矩陣,完全關聯矩陣,三元組都可以直接在計算機中表示.特殊的圖有歐拉圖和哈密爾頓圖。最短路徑問題是圖論中的一個典范問題，它已經被應用于眾多領域.最短路徑問題最直接的應用當數在地理信息領域，如：GIS網絡分析、城市規(guī)劃、電子導航等.在交通咨詢方面，尋找交通路網中兩個城市間最短的行車路線就是最短路徑問題的一個典型的例子.1.4重點工作由于最短路徑問題的廣泛應用，很多學者都對此進行了深入的研究，也產生了一些經典的算法.近些年來，對最短路徑研究的熱度依然不減，并且時間復雜度降得越來越低.所以在本論文中我將分析比較我們學習過的一些經典的最短路徑算法

11、，我還將提出一些改進這些算法的思路.最后還會設計實現經典的Dijkstra算法的程序.第二章 最短路徑問題的基礎知識2.1 圖的基本概念V1V2V3V4V5圖1圖：圖是一種較線形表和樹更為復雜的數據結構。在圖形結構中，結點之間的關系可以是任意的，圖中任意兩個數據元素之間都可能相關。在圖中數據元素通常叫做頂點.說明：在保持圖的點邊關系不變的情況下，圖形的位置、大小、形狀都是無關緊要的.圖1就是一個典型的圖?；。?兩個頂點之間關系的集合VR,<v,w>VR,表示從v到w的一條弧。稱v為弧尾，w為弧頭。若<v,w> 為一條有向弧，則稱該圖為有向圖；若（v,w）為無向弧，此時的

12、圖稱為無向圖。完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。在有向圖中，如果任意兩項頂點之間都存在方向互為相反的兩條弧，則稱該圖為由向完全圖。稀疏圖、稠密圖：由很少邊的圖稱為稀疏圖。反之，成為稠密圖。稀疏和稠密本身是模糊的概念，稀疏和稠密常常是相對而言的。鄰接點：對于無向圖G=（V，E），如果邊（v,w）E,則稱頂點v和w互為鄰接點。度：以頂點v為頭的弧的數目稱為v的入度，以頂點v為尾的弧的數目稱為v的出度，出度和入度統稱為度。路徑：無向圖G=（V，E）中從頂點v到頂點w的路徑是一個頂點序列其中 E，1 <j< m 。如果G是有向圖，則路徑也是有向的，路經

13、的長度是路徑上的邊數或弧的數目，第一個頂點和最后一個頂點相同的路徑稱之為回路或環(huán)。簡單路徑：序列中頂點不重復出現的路徑稱為簡單路徑。除了第一個和最后一個頂點之外，其余頂點不重復出現的回路，稱之為簡單回路或簡單環(huán)。圖連通： 在無向圖G中，如果從頂點v到頂點w有路徑，則稱頂點v到頂點w 是連通的。對于任意兩個頂點都是連通的，則稱圖G是連通圖。在有向圖G中，對于每一對頂點E都存在，則稱G是強連通圖。鄰接表：是圖的一種鏈式存儲結構。在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中結點表示依附于頂點的邊。每個結點有3個域組成，其中鄰接點域指示與頂點鄰接的點在圖中的位置，鏈域指示下一條邊或弧的結點

14、；數據域存儲和邊或弧相關的信息，如權值等。每個鏈表上附設一個表頭結點。在表頭結點中，除了沒有鏈域指向鏈表中第一個結點之外，還沒有存儲頂點的名或其他有關信息的數據域。如下圖2所示： 表結點 頭結點 datafirstarcadjvex nextarc info 圖22.2圖的遍歷從圖中的某一頂點出發(fā)，按某種搜索方法訪遍其余頂點，且使每一頂點僅被訪問一次，這一過程稱為圖的遍歷。通過圖的遍歷，我們可以得到圖的很多信息，圖的遍歷是圖算法領域的核心。圖的常用遍歷方法有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。2.2.1深度優(yōu)先搜索深度優(yōu)先搜索如同它的名稱所暗示的那樣，這種搜索算法所遵循的搜素

15、策略是盡可能“深”地搜索一個圖，深度優(yōu)先搜索類似樹的先序遍歷。算法思想：對于圖G=（V，E），首先訪問指定的起始頂點S，然后訪問與S鄰接且未被訪問的任一頂點W1,再訪問與W1鄰接且未被訪問的任一頂點W2，重復上述過程。當不能再繼續(xù)向下訪問時，退回到上一個最近被訪問的頂點，若它還有鄰接頂點未被訪問過。則從該點開始繼續(xù)上述搜索過程，直到圖中所有頂點均被訪問過為止。算法 圖的深度優(yōu)先搜索算法void DFSTraverse(Graph G) for(i=0;i<G.vexnum;i+) visitedi=0; / 初始化每個結點的訪問標記 for(i=0;i<G.vexnum;i+) i

16、f(visitedi=0) DFS(G,i); / 選用DFS_AL或DFS_M2.2.2廣度優(yōu)先搜索廣度優(yōu)先搜索是一種分層的查找過程。它類似于二叉樹的層序遍歷。每向前走一步可能訪問一批項點，它不是一個遞歸的算法。為了實現逐層的訪問，算法必須借助一個輔助隊列，以記憶正在訪問的頂點的下一層頂點。算法思想:對于圖G=(V,E)，首先訪問起始頂點V，再依次訪問V的各個未訪問過的鄰接頂點W1，W2，Wi，然后再依次訪問W1，W2，Wi的所有未被訪問過的鄰接頂點，依次類推，直到圖中所有頂點都被訪問過為止。算法 圖的廣度優(yōu)先搜索算法void DFSTraverse(Graph G) for(i=0;i&l

17、t;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）發(fā)明的。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，該算法可以用來找到兩個城市之間的最短路徑。該算法的輸入包含了一個有權重的有向圖 G，以及G中

18、的一個來源頂點 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算法是一種求單源最短路的算法，即從一個點開始到所有其他點的最短路。其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由于不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了算法的正確性。不過根據這個原理，用Dijkst

20、ra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質3.1.2 算法描述這個算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。初始時，原點 s 的路徑長度值被賦為 0 （ds = 0），若存在能直接到達的邊（s,m），則把dm設為w（s,m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對于 V 中所有頂點 v 除 s 和上述 m 外 

21、dv = ）。當算法結束時，dv 中儲存的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話是無窮大。 Dijkstra 算法的基礎操作是邊的拓展：如果存在一條從 u 到 v 的邊，那么從 s 到 v 的最短路徑可以通過將邊（u, v）添加到尾部來拓展一條從 s 到 u 的路徑。這條路徑的長度是 du + w(u, v)。如果這個值比目前已知的 dv 的值要小，我們可以用新值來替代當前 dv 中的值。拓

22、展邊的操作一直執(zhí)行到所有的 dv 都代表從 s 到 v 最短路徑的花費。這個算法經過組織因而當 du 達到它最終的值的時候每條邊（u, v）都只被拓展一次。算法維護兩個頂點集 S 和 Q。集合 S 保留了我們已知的所有 dv 的值已經是最短路徑的值頂點，而集合 Q 則保留其他所有頂點。集合S初始狀態(tài)為空，而后每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 du 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，算法對每條外接邊 (u, v) 進行拓展。3.1.3算法步驟1. 初使時令 S=V0,T=其余頂點，T中頂點對應的距離值若存

23、在<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 中節(jié)點A 到其它各節(jié)點的最優(yōu)路徑.GK 20 2.9 3.2D 18N 4.4 3.5 3.2 4.5B 1

24、6HE 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次表1采用Dijkstra 算法求解A到其他各節(jié)點最優(yōu)路徑的過程

25、序號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.016.113-13.7/H-15.916.114-15.9

26、/L16.118.715-16.1/M Dijkstra算法的不足算法的運行時間是 O(n2)，在現行電子地圖中，網絡模型的規(guī)模常常較大，節(jié)點數多達上千或上萬，并且對網絡模型的查詢也要求實時性，因此Dijkstra 算法雖然在理論上是可行的，但在實際應用中不盡人意，當網絡模型中節(jié)點數和邊數較多的情況下，算法的計算量較大時間花費較多效率非常低。3.1.6 改進Dijkstra 算法的基本思想及實現表1 中的數值大多數是，都是無用運算，如果節(jié)點數量很大，將極其浪費運算時間.由于，節(jié)點是否在上次已經被計算出最短路徑未知，當前節(jié)點是否與節(jié)點是否相連也未知，也就是 未知，這時

27、是已知的，故本次計算的 到底是不是，取決于上一步數值和的數值，從表達式可以看出，只要這兩個數值不都是，本次計算的 就不會是，所以在上面Dijkstra 算法的實現步驟第(2) 步時，先判斷一下，只要原來的， 的數值中至少有一個不是，才進行下面的計算，這樣就保證了當預見 是時，不對它進行計算，避免了大量無效的計算，提高了搜索效率。3.2 bellman-ford算法是由 Richard Bellman 和 Lester Ford 創(chuàng)立的，求解單源最短路徑問題的一種算法。有時候這種算法也被稱為 Moore-Bellman-Ford 算法，因為 Edward F. Moore 也為這個算法的發(fā)展做出

28、了貢獻。它的原理是對圖進行V-1次松弛操作，得到所有可能的最短路徑。3.2.1算法原理它的原理是對圖進行V-1次松弛操作，得到所有可能的最短路徑。松弛：每次松弛操作實際上是對相鄰節(jié)點的訪問，第n次松弛操作保證了所有深度為n的路徑最短。由于圖的最短路徑最長不會經過超過條邊，所以可知貝爾曼-福特算法所得為最短路徑。負邊權操作：與迪科斯徹算法不同的是，迪科斯徹算法的基本操作“拓展”是在深度上尋路，而“松弛”操作則是在廣度上尋路，這就確定了貝爾曼-福特算法可以對負邊進行操作而不會影響結果。負權環(huán)判定：因為負權環(huán)可以無限制的降低總花費，所以如果發(fā)現第n次操作仍可降低花銷，就一定存在負權環(huán)。3.2.2算法

29、描述對有向圖G(V,E) ，用貝爾曼-福特算法求以Vs為源點的最短路徑的過程：1. 建立dist ，表示目前已知源點到各個節(jié)點的最短距離，起始值dists=0 ，其余皆為。2. 建立Pred ，Pred 表示某節(jié)點路徑上的父節(jié)點，起始值皆為NULL。3. 對(Vi,Vj)E ，比較distVi+(Vi,Vj) 和distVj ,并將小的賦給distVj ，如果修改了distV_j則PredVj= Vi（松弛操作）4. 重復以上操作V-1 次5. 再重復操作2一次，如distVj>distVi+(Vi,Vj) ,則此圖存在負權環(huán)3.2.3 bellman-ford算法的優(yōu)缺點其優(yōu)于Dijk

30、stra算法的方面是邊的權值可以為負數、實現簡單。但缺點是時間復雜度過高，高達O(V E)。由此算法優(yōu)化得到了多種單源最短路徑問題的高效算法，如取隊列優(yōu)化而得的SPFA算法。3.2.4 bellman-ford算法的優(yōu)化在實際操作中，貝爾曼-福特算法經常會在未達到V-1次前就出解，V-1其實是最大值。于是可以在循環(huán)中設置判定，在某次循環(huán)不再進行松弛時，直接退出循環(huán)，進行負權環(huán)判定。基于Bellman-Ford算法，提出SPFA(Shortest Path Faster Algorithm)算法，它是Bellman-Ford算法的一種隊列實現，減少了不必要的冗余計算。SPFA算法有兩個優(yōu)化算法

31、SLF 和 LLL： SLF：Small Label First 策略，設要加入的節(jié)點是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的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現，通常使用效率更加穩(wěn)定的Dijkstra算法。3

32、.3 Floyd算法Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權圖中頂點間最短路徑的算法。3.3.1 算法原理Floyd-Warshall算法的原理是動態(tài)規(guī)劃。設Di,j,k為從i到j的只以(1k)集合中的節(jié)點為中間節(jié)點的最短路徑的長度。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)。在實際算法中，為了節(jié)約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。3.3.2算法描述Floyd算法的描

33、述如下：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算法的優(yōu)缺點Floyd算法適用于APSP(All Pairs Shortest Paths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環(huán)結構緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。 優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單 缺

34、點：時間復雜度比較高，不適合計算大量數據。第四章 設計實現經典Dijkstra算法城市交通是一個城市的命脈。它是城市社會和經濟活動的重要組成部分。伴隨著國民經濟和城市建設的快速發(fā)展，城市經濟的繁榮，人口的增加，城市必須解決好人們出行的需求。城市交通直接關系著城市的經濟發(fā)展和居民生活，對城市經濟具有全局性、先導性的影響。但是隨著城市的發(fā)展，道路交通越來越復雜人們很難得到最佳出行路線，這樣給一些人的出行就帶來了不便。因此，急需一個方便、快捷的最短路徑算法，本文通過對最短路徑算法的研究，編寫了一個基于Dijkstra算法的程序。4.1程序運行環(huán)境1. 操作系統要求：windows xp/window

35、s 20002. 需要的軟件： Visual Studio C+6.03. 計算機硬件要求：800MHZ奔騰 獲其他處理器，256以上的內存4.2開發(fā)語言簡介1VisualC+簡介VisualC+是微軟開發(fā)的一個集成環(huán)境，是使用C+的一個平臺。它是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C+1.0后，隨著其新版本的不斷問世，Visual C+已成為專業(yè)程序員進行軟件開發(fā)的首選工具。Visual C+6.0不僅是一個C+編譯器，而且是一個基于Windows操作系統的可視化集成開發(fā)環(huán)境（Integrated Development Environmen

36、t,IDE）。Visual C+6.0由許多組件組成，包括編輯器、調試器以及程序向導AppWizard、類向導Class Wizard等開發(fā)工具。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。2. MFC基礎類類MFC,微軟基礎類(Microsoft Foundation Classes)，同VCL類似，是一種Application Framework，隨微軟Visual C+ 開發(fā)工具發(fā)布。該類庫提供一組通用的可重用的類庫供開發(fā)人員使用。大部分類均從CObject 直接或間接派生，只有少部分類例外。MFC 應用程序的總體結構通常由 由開發(fā)人員從MFC類派生

37、的幾個類和一個CWinApp類對象（應用程序對象）組成。MFC 提供了MFC AppWizard 自動生成框架。Windows 應用程序中，MFC 的主包含文件為"Afxwin.h"。MFC,微軟基礎類(Microsoft Foundation Classes),實際上是微軟提供的,用于在C+環(huán)境下編寫應用程序的一個框架和引擎,VC+是WinDOS下開發(fā)人員使用的專業(yè)C+ SDK(SDK,Standard SoftWare Develop Kit,專業(yè)軟件開發(fā)平臺),MFC就是掛在它之上的一個輔助軟件開發(fā)包，是對WindowsAPI的封裝，大約有100多個類，但常用的有二三

38、十種?，F在介紹一下MFC中比較重要也較常用的類。CWnd：窗口類，它是大多數“看得見的東西”的父類，比如視圖CView、框架窗口CFrameWnd、工具條CToolBar、對話框CDialog、按鈕CButton等。 CDocument文檔，負責內存數據與磁盤的交互。最重要的是OnOpenDocument(讀入),OnSaveDocument（寫盤）,Serialize（讀寫） Cview：視圖類，負責內存數據與用戶的交互。包括數據的顯示、用戶操作的響應(如菜單的選取、鼠標的響應）。最重要的是OnDraw(重畫窗口)，通常用CWnd:Invalidate()來啟動它。另外，它通過消息映射表處理

39、菜單、工具條、快捷鍵和其他用戶消息。 CDC：設備文本類。無論是顯示器還是打印機，都是畫圖給用戶看。這圖就抽象為CDC類來完成。 Cdialog：對話框類。它是所有對話框的類。CwinApp：應用程序類。似于C中的main函數，是程序執(zhí)行的入口和管理者，負責程序建立、消滅，主窗口和文檔模板的建立。CGdiObject及子類,用于向設備文本畫圖。它們都需要在使用前選進DC。 Cbrush：刷子，填充 Cfont：字體，控制文字輸出的字體 。Cfile：文件。最重要的不外是Open（打開）,Read（讀入）,Write（寫） Cstring：字符串。封裝了C中的字符數組，非常實用。 4.3 可行性

40、分析可行性分析（Feasibility Analysis）也稱為可行性研究，是在系統調查的基礎上，針對新系統的開發(fā)是否具備必要性和可能性，對新系統的開發(fā)從技術、經濟、社會的方面進行分析和研究，以避免投資失誤，保證新系統的開發(fā)成功?？尚行匝芯康哪康木褪怯米钚〉拇鷥r在盡可能短的時間內確定問題是否能夠解決。本系統對機器本身沒有太高的要求，一般普通電腦完全可滿足要求。對于軟件技術要求，現在基于VisualC+ MFC架構的程序設計語言已非常成熟，從剛開始的C，到現在的MFC,C#的百花齊放，再到微軟最新推出不久ASP.NET使用其中任何一門語言開發(fā)都可以滿足要求?？衫矛F有的電腦，裝上VisualC+

41、 6.0軟件，即可成編寫該系統，對自己無經濟的負擔，在經濟上完全可行。本系統開發(fā)不會侵犯他人、集體或國家利益，不存在侵權等問題，不違反國家法律,因此具有法律可行性。綜上所述，技術上、經濟上、法律上都是可行的,而且要求不高，所以該系統的開發(fā)是可行的。4.4需求分析需求分析簡單地說就是分析用戶的需求。需求分析的任務是通過詳細調查現實世界要處理的對象（組織、部門、企業(yè)等），充分了解原系統（手工系統或計算機系統）工作概況，明確用戶的各種需求，然后在此基礎上確定新系統的功能?，F在城市發(fā)展越來越快，交通網絡也越來越復雜，人們出行會有很多條路線選擇，怎么樣選擇才能找出最短路徑？是人們目前迫切的需要。 4.5

42、 軟件結構本系統的軟件結構比較簡單，主要有三大部分組成：地圖導入模塊，導航模塊和信息查詢。如圖4所示： 出行導航系統地圖導入模塊信息查詢導航模塊圖4 軟件結構4.6 模塊詳細設計與實現在前面的軟件結構中，已將軟件劃分為多個模塊，并將它們按照一定的原則組裝起來，同時確定了每個功能及模塊之間的外部接口?，F在所要做的就是確定每個模塊具體執(zhí)行過程，也可以說是“過程設計”。在處理過程設計時我采用的是結構化程序設計（簡稱SP）方法。需要指出的是系統的詳細設計并不是指具體的編程序，而是將概要設計階段產生的系統功能模塊圖細化成很容易產生程序的圖紙。因此詳細設計的結果基本決定了最終程序的質量。為軟件的質量，延長

43、軟件的生存期，軟件的可測試性、可維護性提供重要的保障。詳細設計階段的根本目標是確定應該怎樣具體的實現所要求的系統，也就是說，經過這個階段的設計工作，應該得出目標系統的精確描述，從而在編碼階段可以把這個描述直接翻譯成用某種程序設計語言書寫的程序。詳細設計的目標不僅僅是邏輯上正確地實現每個模塊的功能，更重要的是設計的處理過程應該盡可能簡明易懂。4.6.1 程序流程圖程序流程圖又稱為程序框圖，它是歷史悠久使用最廣泛的描述軟件設計的方法。1.下面是程序的流程圖。開始導入地圖Y導航N選擇地點顯示路線Y是否退出N結束圖5程序流程圖4.6.2 各模塊設計這個應用軟件落實到具體的實現上時，首先要進行界面的設計

44、，界面的功能布局是否合理、美觀與否都關乎到這個軟件質量。所以軟件的界面也是很重要的一部分。這部分都做完以后剩下的就是編程了，這是所有預想功能能否實現的關鍵所在，也是設計難點。下面具體介紹各部分是怎么實現的。設計開始首先要建立一個基于對話框的MFC工程類，這樣系統會默認生成一個基本的對話框架。里面包含確定和取消兩個按鈕，我們根據自己的需要進行增刪。這個查詢系統的主要模塊有三個，一個是地圖導入模塊，第二個是導航模塊，另一個是信息查詢模塊。這三個模塊我做到了一起，這樣比較方便用戶操作。具體幾面如下圖所示。地圖導入模塊地圖導入模塊包含一個打開文件對話框,對話框里面有選擇地圖文件，也就是說可以選擇不同的

45、地圖打開。具體界面如下圖所示。導航模塊 信息查詢模塊信息結查詢果顯示導航結果顯示（紅色線條顯示）4.7系統特色本系統根據出行人實際需求和需要進行設計和開發(fā)。 該系統功能基本上滿足人們日常出行的需求。本次畢業(yè)設計的課題是基于最短路徑研究的基礎上開發(fā)的系統,可實現最短路徑轉乘查詢功能。在具體實現本次設計時，采用C+編程語言，采用MFC類具有很好的圖形化界面，操作簡單，使用方便。系統的設計充分考慮了使用人員、用戶的使用習慣，操作簡單，方便靈活。4.8 系統需要改進的地方這是我首次用C+語言結合微軟MFC類進行完整系統的開發(fā)，一切都是從零開始學習，所以開發(fā)的時候難免會過于簡單，考慮的也不是很周到。同時由于時間倉促，有些功能的實現不是很完美。系統在設計過程中不可避免地遇到了各種各樣的問題，由于整個系統完全都是由個人設計的，有關MFC類許多細節(jié)問題都要靠自己去摸索，加之本人