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

1、目錄目錄1摘要2Abstract3第一章緒論41.1課題背景41.2目的意義51.3國(guó)內(nèi)外現(xiàn)狀51.4重點(diǎn)工作6第二章 最短路徑問題的基礎(chǔ)知識(shí)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 算法的基本思想及實(shí)現(xiàn)143.2 bellman-ford算法14算法原理14算法描述153.2.3 bellman-ford算法的優(yōu)缺點(diǎn)153.2.4

2、bellman-ford算法的優(yōu)化153.3 Floyd算法163.3.1 算法原理16算法描述163.3.3 Floyd算法的優(yōu)缺點(diǎn)17第四章 設(shè)計(jì)實(shí)現(xiàn)經(jīng)典Dijkstra算法184.1程序運(yùn)行環(huán)境184.2開發(fā)語(yǔ)言簡(jiǎn)介184.3 可行性分析204.4需求分析204.5 軟件結(jié)構(gòu)214.6 模塊詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)214.6.1 程序流程圖224.6.2 各模塊設(shè)計(jì)224.7系統(tǒng)特色254.8 系統(tǒng)需要改進(jìn)的地方25第五章 結(jié)論265.1 最短路徑算法265.2 心得與收獲26致謝27參考文獻(xiàn)28摘要隨著社會(huì)的進(jìn)步，科技的飛速發(fā)展，人們的辦事效率也得到了極大的提高，在當(dāng)今的社會(huì)里，花費(fèi)最小的代價(jià)收

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、在<V0,Vi>，d(Vi)為<V0,Vi>弧上的權(quán)值 若不存在<V0,Vi>，d(Vi)為2. 從T中選取一個(gè)其距離值為最小的頂點(diǎn)W且不在S中，加入S 3. 對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值 4. 重復(fù)上述步驟2、3，直到S中包含所有頂點(diǎn)，即S=T為止3.1.4 Dijkstra算法的應(yīng)用舉例以具體實(shí)例說(shuō)明Dijkstra 算法的具體應(yīng)用.例1. 利用Dijkstra 算法求圖3 中節(jié)點(diǎn)A 到其它各節(jié)點(diǎn)的最優(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 算法的實(shí)現(xiàn)步驟其計(jì)算過程可歸納為表1 所示.從表1 中可以看出從 到 的最短路徑為 且到的距離為=18.3 在求到最短路徑的過程中到其余各點(diǎn)的最短路徑也相應(yīng)求出.若以計(jì)算一次為計(jì)算單位，則利用Dijkstra算法計(jì)算 到 最短路徑時(shí)所需的計(jì)算次數(shù)= 15+14+13+ +2 = 119次表1采用Dijkstra 算法求解A到其他各節(jié)點(diǎn)最優(yōu)路徑的過程

25、序號(hào)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算法的不足算法的運(yùn)行時(shí)間是 O(n2)，在現(xiàn)行電子地圖中，網(wǎng)絡(luò)模型的規(guī)模常常較大，節(jié)點(diǎn)數(shù)多達(dá)上千或上萬(wàn)，并且對(duì)網(wǎng)絡(luò)模型的查詢也要求實(shí)時(shí)性，因此Dijkstra 算法雖然在理論上是可行的，但在實(shí)際應(yīng)用中不盡人意，當(dāng)網(wǎng)絡(luò)模型中節(jié)點(diǎn)數(shù)和邊數(shù)較多的情況下，算法的計(jì)算量較大時(shí)間花費(fèi)較多效率非常低。3.1.6 改進(jìn)Dijkstra 算法的基本思想及實(shí)現(xiàn)表1 中的數(shù)值大多數(shù)是，都是無(wú)用運(yùn)算，如果節(jié)點(diǎn)數(shù)量很大，將極其浪費(fèi)運(yùn)算時(shí)間.由于，節(jié)點(diǎn)是否在上次已經(jīng)被計(jì)算出最短路徑未知，當(dāng)前節(jié)點(diǎn)是否與節(jié)點(diǎn)是否相連也未知，也就是 未知，這時(shí)

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

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

29、描述對(duì)有向圖G(V,E) ，用貝爾曼-福特算法求以Vs為源點(diǎn)的最短路徑的過程：1. 建立dist ，表示目前已知源點(diǎn)到各個(gè)節(jié)點(diǎn)的最短距離，起始值dists=0 ，其余皆為。2. 建立Pred ，Pred 表示某節(jié)點(diǎn)路徑上的父節(jié)點(diǎn)，起始值皆為NULL。3. 對(duì)(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)缺點(diǎn)其優(yōu)于Dijk

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

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

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

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

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

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

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

38、十種?，F(xiàn)在介紹一下MFC中比較重要也較常用的類。CWnd：窗口類，它是大多數(shù)“看得見的東西”的父類，比如視圖CView、框架窗口CFrameWnd、工具條CToolBar、對(duì)話框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()來(lái)啟動(dòng)它。另外，它通過消息映射表處理

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

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

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

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

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

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

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