【正文】 ............................................................................26五、設(shè)計總結(jié) .............................................................................................28V致謝 ............................................................................................................29參 考 文 獻(xiàn) ...............................................................................................29交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)內(nèi) 容 摘 要目前在交通咨詢領(lǐng)域，最短路徑算法的研究和應(yīng)用越來越多，其中最短路徑算法的效率問題是普遍關(guān)注并且在實際應(yīng)用中迫切需要解決的問題。隨著現(xiàn)代生活節(jié)奏的加快，以及城市汽車數(shù)量的不斷增加，交通網(wǎng)絡(luò)也越來越發(fā)達(dá)，在交通工具和交通方式不斷更新的今天，人們在旅游、出差或者其他出行時，不僅會關(guān)心費用問題，而且對里程和所需要的時間等問題也特別感興趣。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問題建立一個交通咨詢系統(tǒng)。這樣的一個交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。本文通過對幾個常見的最短路徑算法的分析，研究和實現(xiàn)，即經(jīng)典的 Dijkstra 算法、Floyd算法。討論了各個算法的思想、原理、實現(xiàn)方法、數(shù)據(jù)結(jié)構(gòu)還有算法描述，并從時間以及空間的復(fù)雜度進(jìn)行分析比較其優(yōu)點和缺陷以及具體的實用性。針對現(xiàn)代交通網(wǎng)絡(luò)現(xiàn)狀特點，分析和研究適合道路的經(jīng)典最短路徑算法，探討了在交通網(wǎng)絡(luò)路線優(yōu)化過程中需要特別處理的幾個問題，并在理論上給出相應(yīng)的合理的解決方案。關(guān)鍵詞：交通咨詢 最短路徑 Dijkstra算法 Floyd算法VIShortest path algorithm of the Transport Advisory System Design and ImplementationAbstractCurrently in the field of traffic advisory, research and application of the shortest path algorithm bee more and more, where in the efficiency of the shortest path algorithm is a mon concern and in practice is an urgent need to solve the problem.With the pace of modern life accelerate, as well as the increasing number of city car, transportation works is more developed, in vehicles and transportation constantly updated today, people in tourism, travel or other travel time, not only concerned about costs, but also the time required mileage and other issues are also of particular interest. To be more convenient for people to travel, we should build a shortest path problem traffic advisory system. Such a transportation system can answer all questions related to transportation have been proposed, such as the shortest path to any one city to other cities, or any shortest path between the two cities.Through the analysis of several mon shortest path algorithm research and realized that the classical Dijkstra algorithm, Floyd algorithm. We discussed various algorithms ideology, theory, implementation, data structures, as well as algorithms described and analyzed to pare their advantages and shortings, and the practicality of the plexity of the specific time and space. For present characteristics of modern transportation work, classical shortest path algorithm analysis and research for the road to explore several issues in transportation work optimization process routes that require special handling, and in theory give the corresponding reasonable solution. Key words：traffic advisory shortest path Dijkstra algorithm Floyd algorithm1序 言最短路徑問題一直在計算機(jī)科學(xué)、交通工程學(xué)、地理信息系統(tǒng)、運(yùn)籌學(xué)等學(xué)科中是一個研究的熱點，它不僅是資源分配問題解決的基礎(chǔ)，更是線路選擇問題解決的基礎(chǔ)，特別是在地圖、車輛調(diào)度以及路由選擇方面有著廣泛的應(yīng)用。最短路徑問題最直接的應(yīng)用當(dāng)數(shù)在地理信息領(lǐng)域中，例如：GIS網(wǎng)絡(luò)分析、城市規(guī)劃、電子導(dǎo)航等等。在交通咨詢方面，尋找交通網(wǎng)路中兩個城市之間最短的行車路線就是最短路徑問題的一個典型的例子。在網(wǎng)絡(luò)通信領(lǐng)域，信息包傳遞的路徑選擇問題也與最短路徑息息相關(guān)。例如OPSF開放路由選擇協(xié)議，每一個OPSF路由器都維護(hù)一個描述自治系統(tǒng)范圍內(nèi)到每個目標(biāo)的最短路徑。在圖像分割問題中，最短路徑也有直接的應(yīng)用：在語音識別中一個主要的問題就是識別同音詞，例如，to、two、too。為解決這個問題，我們需要建立一個圖，頂點代表可能的單詞，扁連接相鄰的單詞，邊上的權(quán)代表相鄰的可能性大小。這樣圖中所表示的最短路徑，就是對句子最好的解釋。由于最短路徑問題的廣泛應(yīng)用，很多學(xué)者都對此進(jìn)行了深入的研究，隨著研究成果的成熟化也是產(chǎn)生了一些經(jīng)典的算法。近年來，對最短路徑研究的熱度依然不減，并且時間復(fù)雜度也降得越來越低。從實際意義上講，沒有哪一種算法能夠適用于所有的網(wǎng)絡(luò)形式，并且在所有的網(wǎng)絡(luò)形式上具有很好的空間和時間復(fù)雜性。這些算法又具有各自的優(yōu)缺點。按照起點終點及路徑的數(shù)據(jù)和特征，最短路徑問題可分為五種類型：兩個節(jié)點間的最短路徑、所有節(jié)點的最短路徑、K則最短路徑、實時最短路徑和指定必經(jīng)點的最短路徑問題。在交通網(wǎng)絡(luò)的路徑分析中，單源最短路徑問題更具有普遍意義，其算法有很多種，其中采用貪心及啟發(fā)策略的Dijkstra算法是目前最完善的，這是荷蘭計算機(jī)科學(xué)教授Edger (19302022)在1959年發(fā)現(xiàn)的一個算法，它以極強(qiáng)的抗差性得到普及和應(yīng)用。再有就是由弗洛伊德（floyd）提出的另一個算法，又稱傳遞閉包方法，求每一對節(jié)點之間的最短路徑。本文就從上述幾類來分別介紹最短路徑的幾種常用算法，并介紹最短路徑問題中的算法改進(jìn)。本文的其它部分組織如下：第一章概述了交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)的目的和意義、選題背景和技術(shù)線路。第二章介紹所要用到的技術(shù)原理。第三章介紹最短路徑問題的幾種算法。第四章交通咨詢系統(tǒng)的設(shè)計及實現(xiàn)。第五章為總結(jié)，提出文章的缺點與不足之處，談?wù)勛约旱南敕?，并提出發(fā)展期望。2一、緒 論（一）課題的背景和意義現(xiàn)如今，我國的各大城市都有著交通擁堵、道路堵塞和交通事故的頻繁發(fā)生，這些都隨著城市私家車的不斷增加和城市汽車交通運(yùn)輸?shù)募涌彀l(fā)展越來越困擾著我們的生活，并且汽車工業(yè)發(fā)展所引發(fā)的道路交通不能滿足實際需求的種種交通問題也越來越嚴(yán)重，越來越突出。為了解決這些問題，除了通常所用的解決辦法，譬如修建必要的道路交通網(wǎng)、針對交通事故多發(fā)路段、修建一系列的交通安全設(shè)施，這些設(shè)施包括道路信號機(jī)、道路標(biāo)識、交通指揮中心等有助于交通安全的設(shè)施，來改善道路的交通環(huán)境，提高交通的順暢性，在一定程度上緩解交通擁擠狀況。而且在必要的時候能夠把道路、車輛、城市的發(fā)展需求等，大都與交通有關(guān)的基本因素歸為一體，在這些基本因素的基礎(chǔ)上，采用信息通信技術(shù)、信息自動采集技術(shù)、電子技術(shù)、網(wǎng)絡(luò)技術(shù)、自動控制以及其他的科學(xué)技術(shù)把它們聯(lián)系起來，開發(fā)一個可供模擬操作的城市交通管理系統(tǒng)。只有將這些方法結(jié)合起來，才能有效地解決隨著交通需求不斷增長、交通系統(tǒng)日益龐大復(fù)雜，所帶來的交通問題。隨著交通網(wǎng)絡(luò)越來越發(fā)達(dá)，人們在旅游、出差或者其他出行時，不僅會關(guān)心費用問題，而且對里程和所需要的時間等問題也特別感興趣。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問題建立一個交通咨詢系統(tǒng)。這樣的一個交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。本題目的意義在于，用 java 軟件技術(shù)實現(xiàn)最短路徑算法在交通咨詢中的重要應(yīng)用，對模擬結(jié)果進(jìn)行分析討論，為將來能夠有效解決各大城市的交通問題提供可靠的依據(jù)。（二）研究現(xiàn)狀本節(jié)闡述三方面問題，首先簡要回顧最短路徑算法研究現(xiàn)狀，然后概要總結(jié)最短路徑算法分類，最后簡單論述最短路徑算法的時間復(fù)雜度。最短路徑問題一直是計算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科領(lǐng)域的研究熱點。國內(nèi)外大量專家學(xué)者對此問題進(jìn)行了深入研究。經(jīng)典的圖論與不斷發(fā)展完善的計算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。常用的路徑規(guī)劃方法有: 平行最短路徑搜索算法，蟻群算法，基于矩陣負(fù)載平衡的啟發(fā)算法, EBSP*算法和 Dijkstra 算法等。創(chuàng)門在空間復(fù)雜度、時間復(fù)雜度、易實現(xiàn)性及應(yīng)用范圍等方面各具3特色但是因為 Dijkstra 算法可以給出最可靠的最短路徑，并且容易實現(xiàn)，所以備受青睞和并被廣泛應(yīng)用。經(jīng)典的 Dijkstra 算法的時間復(fù)雜度為 ，直接應(yīng)用到大規(guī)模城市路網(wǎng)時，最短路徑查詢時間難以令人接受，專家學(xué)者紛紛開展 Dij kstra 優(yōu)化算法研究，概括起來，以往研究者主要是從5 個方面對最短路徑算法進(jìn)行性能優(yōu)化：(1)基于數(shù)據(jù)存儲結(jié)構(gòu)的優(yōu)化，以空間換取時間； ( 2 )基于路網(wǎng)規(guī)?？刂频膬?yōu)化；(3)基于搜索策略的優(yōu)化；( 4 )優(yōu)先級隊列結(jié)構(gòu)的優(yōu)化； ( 5 )基于雙向搜索的并行計算優(yōu)化。本文所研究的算法內(nèi)容融合了除(4)之外的所有優(yōu)化策略，首先采用堆數(shù)據(jù)結(jié)構(gòu)將 Dijkstra 算法時間復(fù)雜度降至 O(N log N)，然后采用橢圓限制算法搜索區(qū)域，控制搜索規(guī)模，限定搜索方向，最后在本文提出的二樹算法中運(yùn)用了并行運(yùn)算思想，極大地降低了最短路徑查詢時間。由于問題類型、網(wǎng)絡(luò)特性的不同，最短路徑算法也表現(xiàn)出多樣性。(1) 按照最短路徑問題分類，最短路徑問題通?？煞譃?2 個基本類型：一是單源最短路徑問題，即查找某一源點到其余各點的最短路徑；另一類是查找某個節(jié)點對之間的最短路徑。最短路徑問題具體可細(xì)分為以下幾種，單源最短路