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

1、目錄目錄1摘要2Abstract3第一章緒論41.1課題背景41.2目的意義51.3國內(nèi)外現(xiàn)狀51.4重點工作6第二章 最短路徑問題的基礎(chǔ)知識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算法的應(yīng)用舉例113.1.5 Dijkstra算法的不足143.1.6 改進(jìn)Dijkstra 算法的基本思想及實現(xiàn)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第四章 設(shè)計實現(xiàn)經(jīng)典Dijkstra算法184.1程序運行環(huán)境184.2開發(fā)語言簡介184.3 可行性分析204.4需求分析204.5 軟件結(jié)構(gòu)214.6 模塊詳細(xì)設(shè)計與實現(xiàn)214.6.1 程序流程圖224.6.2 各模塊設(shè)計224.7系統(tǒng)特色254.8 系統(tǒng)需要改進(jìn)的地方25第五章 結(jié)論265.1 最短路徑算法265.2 心得與收獲26致謝27參考文獻(xiàn)28摘要隨著社會的進(jìn)步，科技的飛速發(fā)展，人們的辦事效率也得到了極大的提高，在當(dāng)今的社會里，花費最小的代價收

3、獲最大的效益，成為了當(dāng)今社會里各行各業(yè)一直信奉的理念，這種理念最直接地體現(xiàn)在求最短路徑的問題上，在生活中最常見的有通信問題、公交網(wǎng)絡(luò)問題、旅游線路設(shè)計與優(yōu)化中的運籌學(xué)問題等。解決這些問題的方法有很多種，但是針對不同的問題哪一種方法才是最優(yōu)的呢?這就是在解決最短路徑問題時首先要解決的問題。求最短路徑的方法有：dijkstra算法、floyd算法、bellman-ford算法、SPFA算法，如果我們能從這些算法中找出解決最短路徑問題的最優(yōu)方法，那么當(dāng)人們再遇到這樣的問題時，就可以節(jié)省很多人力物力，極大地提高了辦事的效率。關(guān)鍵詞：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課題背景近年來，隨著社會經(jīng)濟(jì)的飛速發(fā)展和人們生活水平的不斷提高，汽

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

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

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

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

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

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

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

15、策略是盡可能“深”地搜索一個圖，深度優(yōu)先搜索類似樹的先序遍歷。算法思想：對于圖G=（V，E），首先訪問指定的起始頂點S，然后訪問與S鄰接且未被訪問的任一頂點W1,再訪問與W1鄰接且未被訪問的任一頂點W2，重復(fù)上述過程。當(dāng)不能再繼續(xù)向下訪問時，退回到上一個最近被訪問的頂點，若它還有鄰接頂點未被訪問過。則從該點開始繼續(xù)上述搜索過程，直到圖中所有頂點均被訪問過為止。算法 圖的深度優(yōu)先搜索算法void DFSTraverse(Graph G) for(i=0;i<G.vexnum;i+) visitedi=0; / 初始化每個結(jié)點的訪問標(biāo)記 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)先搜索是一種分層的查找過程。它類似于二叉樹的層序遍歷。每向前走一步可能訪問一批項點，它不是一個遞歸的算法。為了實現(xiàn)逐層的訪問，算法必須借助一個輔助隊列，以記憶正在訪問的頂點的下一層頂點。算法思想:對于圖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; / 訪問標(biāo)記數(shù)組初始化 for(i=0;i<G.vexnum;i+) if( ! visitedi ) BFS(G,i); / Vi未訪問過。從Vi開始BFS搜索第三章 最短路徑算法3.1 Dijkstra算法由荷蘭計算機(jī)科學(xué)家艾茲赫爾·戴克斯特拉（Edsger Wybe Dijkstra）發(fā)明的。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權(quán)重表示著城市間開車行經(jīng)的距離，該算法可以用來找到兩個城市之間的最短路徑。該算法的輸入包含了一個有權(quán)重的有向圖 G，以及G中

18、的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù) w: E  0, 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負(fù)花費值（cost）。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。

19、已知有V 中有頂點 s 及 t，Dijkstra 算法可以找到 s 到 t 的最低花費路徑(例如，最短路徑)。這個算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。3.1.1 算法原理Dijkstra算法是一種求單源最短路的算法，即從一個點開始到所有其他點的最短路。其基本原理是：每次新擴(kuò)展一個距離最短的點，更新與其相鄰的點的距離。當(dāng)所有邊權(quán)都為正時，由于不會存在一個距離更短的沒擴(kuò)展過的點，所以這個點的距離永遠(yuǎn)不會再被改變，因而保證了算法的正確性。不過根據(jù)這個原理，用Dijkst

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

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

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

23、在<V0,Vi>，d(Vi)為<V0,Vi>弧上的權(quán)值 若不存在<V0,Vi>，d(Vi)為2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S 3. 對T中頂點的距離值進(jìn)行修改：若加進(jìn)W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值 4. 重復(fù)上述步驟2、3，直到S中包含所有頂點，即S=T為止3.1.4 Dijkstra算法的應(yīng)用舉例以具體實例說明Dijkstra 算法的具體應(yīng)用.例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相應(yīng)的權(quán)值為： 根據(jù)Dijkstra 算法的實現(xiàn)步驟其計算過程可歸納為表1 所示.從表1 中可以看出從 到 的最短路徑為 且到的距離為=18.3 在求到最短路徑的過程中到其余各點的最短路徑也相應(yīng)求出.若以計算一次為計算單位，則利用Dijkstra算法計算 到 最短路徑時所需的計算次數(shù)= 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)，在現(xiàn)行電子地圖中，網(wǎng)絡(luò)模型的規(guī)模常常較大，節(jié)點數(shù)多達(dá)上千或上萬，并且對網(wǎng)絡(luò)模型的查詢也要求實時性，因此Dijkstra 算法雖然在理論上是可行的，但在實際應(yīng)用中不盡人意，當(dāng)網(wǎng)絡(luò)模型中節(jié)點數(shù)和邊數(shù)較多的情況下，算法的計算量較大時間花費較多效率非常低。3.1.6 改進(jìn)Dijkstra 算法的基本思想及實現(xiàn)表1 中的數(shù)值大多數(shù)是，都是無用運算，如果節(jié)點數(shù)量很大，將極其浪費運算時間.由于，節(jié)點是否在上次已經(jīng)被計算出最短路徑未知，當(dāng)前節(jié)點是否與節(jié)點是否相連也未知，也就是 未知，這時

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

28、了貢獻(xiàn)。它的原理是對圖進(jìn)行V-1次松弛操作，得到所有可能的最短路徑。3.2.1算法原理它的原理是對圖進(jìn)行V-1次松弛操作，得到所有可能的最短路徑。松弛：每次松弛操作實際上是對相鄰節(jié)點的訪問，第n次松弛操作保證了所有深度為n的路徑最短。由于圖的最短路徑最長不會經(jīng)過超過條邊，所以可知貝爾曼-福特算法所得為最短路徑。負(fù)邊權(quán)操作：與迪科斯徹算法不同的是，迪科斯徹算法的基本操作“拓展”是在深度上尋路，而“松弛”操作則是在廣度上尋路，這就確定了貝爾曼-福特算法可以對負(fù)邊進(jìn)行操作而不會影響結(jié)果。負(fù)權(quán)環(huán)判定：因為負(fù)權(quán)環(huán)可以無限制的降低總花費，所以如果發(fā)現(xiàn)第n次操作仍可降低花銷，就一定存在負(fù)權(quá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. 重復(fù)以上操作V-1 次5. 再重復(fù)操作2一次，如distVj>distVi+(Vi,Vj) ,則此圖存在負(fù)權(quán)環(huán)3.2.3 bellman-ford算法的優(yōu)缺點其優(yōu)于Dijk

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

31、SLF 和 LLL： SLF：Small Label First 策略，設(shè)要加入的節(jié)點是j，隊首元素為i，若dist(j)<dist(i)，則將j插入隊首，否則插入隊尾。 LLL：Large Label Last 策略，設(shè)隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)>x則將i插入到隊尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出對進(jìn)行松弛操作。 SLF 可使速度提高 15 20%；SLF + LLL 可提高約 50%。 在實際的應(yīng)用中SPFA的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。3

32、.3 Floyd算法Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。3.3.1 算法原理Floyd-Warshall算法的原理是動態(tài)規(guī)劃。設(shè)Di,j,k為從i到j(luò)的只以(1k)集合中的節(jié)點為中間節(jié)點的最短路徑的長度。1.若最短路徑經(jīng)過點k，則Di,j,k=Di,j,k-1+ Di,j,k-1。2.若最短路徑不經(jīng)過點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é)約空間，可以直接在原來空間上進(jìn)行迭代，這樣空間可降至二維。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的代價，當(dāng)Di,j為 表示兩點之間沒有任何連接。3.3.3 Floyd算法的優(yōu)缺點Floyd算法適用于APSP(All Pairs Shortest Paths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。 優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單 缺

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

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

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

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

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

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

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

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

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

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

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

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