交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)畢業(yè)論文

PAGE 本科畢業(yè)論文(設計)論文題目：交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)PAGE31 畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得及其它教育機構的學位或學歷而使用過的材料。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。作者簽名：日期：指導教師簽名：日期：使用授權說明本人完全了解大學關于收集、保存、使用畢業(yè)設計（論文）的規(guī)定，即：按照學校要求提交畢業(yè)設計（論文）的印刷本和電子版本；學校有權保存畢業(yè)設計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務；學?？梢圆捎糜坝?、縮印、數(shù)字化或其它復制手段保存論文；在不以贏利為目的前提下，學?？梢怨颊撐牡牟糠只蛉績?nèi)容。作者簽名：日期：

學位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導師的指導下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。作者簽名： 日期：年月日學位論文版權使用授權書本學位論文作者完全了解學校有關保留、使用學位論文的規(guī)定，同意學校保留并向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權大學可以將本學位論文的全部或部分內(nèi)容編入有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。涉密論文按學校規(guī)定處理。作者簽名： 日期：年月日導師簽名：日期：年月日

注意事項1.設計（論文）的內(nèi)容包括：1）封面（按教務處制定的標準封面格式制作）2）原創(chuàng)性聲明3）中文摘要（300字左右）、關鍵詞4）外文摘要、關鍵詞5）目次頁（附件不統(tǒng)一編入）6）論文主體部分：引言（或緒論）、正文、結論7）參考文獻8）致謝9）附錄（對論文支持必要時）2.論文字數(shù)要求：理工類設計（論文）正文字數(shù)不少于1萬字（不包括圖紙、程序清單等），文科類論文正文字數(shù)不少于1.2萬字。3.附件包括：任務書、開題報告、外文譯文、譯文原文（復印件）。4.文字、圖表要求：1）文字通順，語言流暢，書寫字跡工整，打印字體及大小符合要求，無錯別字，不準請他人代寫2）工程設計類題目的圖紙，要求部分用尺規(guī)繪制，部分用計算機繪制，所有圖紙應符合國家技術標準規(guī)范。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準用徒手畫3）畢業(yè)論文須用A4單面打印，論文50頁以上的雙面打印4）圖表應繪制于無格子的頁面上5）軟件工程類課題應有程序清單，并提供電子文檔5.裝訂順序1）設計（論文）2）附件：按照任務書、開題報告、外文譯文、譯文原文（復印件）次序裝訂

目錄 序言 1一、緒論 2（一）課題的背景和意義 2（二）研究現(xiàn)狀 21.最短路徑算法研究現(xiàn)狀 22.最短路徑算法分類 33.算法時間復雜度 3（三）研究內(nèi)容 4（四）論文結構 4二、最短路徑算法相關原理 4（一）Dijkstra算法 41.算法思想分析 52.實現(xiàn)思路 53.計算步驟 5（二）Floyd算法 71.算法思想原理： 82.算法描述： 83.Floyd算法過程矩陣的計算十字交叉法 8三、開發(fā)工具與環(huán)境 10（一）Java技術 101.Java簡介 102.Java的處理流程 11四、交通咨詢系統(tǒng)的實現(xiàn) 11（一）系統(tǒng)分析 111.系統(tǒng)的設計內(nèi)容： 112.系統(tǒng)的設計思想 123.系統(tǒng)設計流程 12（二）系統(tǒng)功能結構 121.系統(tǒng)構架設計 122.系統(tǒng)詳細設計 143.測試數(shù)據(jù)及分析 26五、設計總結 28致謝 29參考文獻 29交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)內(nèi)容摘要目前在交通咨詢領域，最短路徑算法的研究和應用越來越多，其中最短路徑算法的效率問題是普遍關注并且在實際應用中迫切需要解決的問題。隨著現(xiàn)代生活節(jié)奏的加快，以及城市汽車數(shù)量的不斷增加，交通網(wǎng)絡也越來越發(fā)達，在交通工具和交通方式不斷更新的今天，人們在旅游、出差或者其他出行時，不僅會關心費用問題，而且對里程和所需要的時間等問題也特別感興趣。為了能夠更方便人們的出行，我們就應該以最短路徑問題建立一個交通咨詢系統(tǒng)。這樣的一個交通系統(tǒng)可以回答人們提出的有關交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。本文通過對幾個常見的最短路徑算法的分析，研究和實現(xiàn)，即經(jīng)典的Dijkstra算法、Floyd算法。討論了各個算法的思想、原理、實現(xiàn)方法、數(shù)據(jù)結構還有算法描述，并從時間以及空間的復雜度進行分析比較其優(yōu)點和缺陷以及具體的實用性。針對現(xiàn)代交通網(wǎng)絡現(xiàn)狀特點，分析和研究適合道路的經(jīng)典最短路徑算法，探討了在交通網(wǎng)絡路線優(yōu)化過程中需要特別處理的幾個問題，并在理論上給出相應的合理的解決方案。關鍵詞：交通咨詢最短路徑Dijkstra算法Floyd算法ShortestpathalgorithmoftheTransportAdvisorySystemDesignandImplementationAbstractCurrentlyinthefieldoftrafficadvisory,researchandapplicationoftheshortestpathalgorithmbecomemoreandmore,whereintheefficiencyoftheshortestpathalgorithmisacommonconcernandinpracticeisanurgentneedtosolvetheproblem.Withthepaceofmodernlifeaccelerate,aswellastheincreasingnumberofcitycar,transportationnetworksismoredeveloped,invehiclesandtransportationconstantlyupdatedtoday,peopleintourism,travelorothertraveltime,notonlyconcernedaboutcosts,butalsothetimerequiredmileageandotherissuesarealsoofparticularinterest.Tobemoreconvenientforpeopletotravel,weshouldbuildashortestpathproblemtrafficadvisorysystem.Suchatransportationsystemcananswerallquestionsrelatedtotransportationhavebeenproposed,suchastheshortestpathtoanyonecitytoothercities,oranyshortestpathbetweenthetwocities.ThroughtheanalysisofseveralcommonshortestpathalgorithmresearchandrealizedthattheclassicalDijkstraalgorithm,Floydalgorithm.Wediscussedvariousalgorithmsideology,theory,implementation,datastructures,aswellasalgorithmsdescribedandanalyzedtocomparetheiradvantagesandshortcomings,andthepracticalityofthecomplexityofthespecifictimeandspace.Forpresentcharacteristicsofmoderntransportationnetwork,classicalshortestpathalgorithmanalysisandresearchfortheroadtoexploreseveralissuesintransportationnetworkoptimizationprocessroutesthatrequirespecialhandling,andintheorygivethecorrespondingreasonablesolution.Keywords：trafficadvisoryshortestpathDijkstraalgorithmFloydalgorithm序言最短路徑問題一直在計算機科學、交通工程學、地理信息系統(tǒng)、運籌學等學科中是一個研究的熱點，它不僅是資源分配問題解決的基礎，更是線路選擇問題解決的基礎，特別是在地圖、車輛調度以及路由選擇方面有著廣泛的應用。最短路徑問題最直接的應用當數(shù)在地理信息領域中，例如：GIS網(wǎng)絡分析、城市規(guī)劃、電子導航等等。在交通咨詢方面，尋找交通網(wǎng)路中兩個城市之間最短的行車路線就是最短路徑問題的一個典型的例子。在網(wǎng)絡通信領域，信息包傳遞的路徑選擇問題也與最短路徑息息相關。例如OPSF開放路由選擇協(xié)議，每一個OPSF路由器都維護一個描述自治系統(tǒng)范圍內(nèi)到每個目標的最短路徑。在圖像分割問題中，最短路徑也有直接的應用：在語音識別中一個主要的問題就是識別同音詞，例如，to、two、too。為解決這個問題，我們需要建立一個圖，頂點代表可能的單詞，扁連接相鄰的單詞，邊上的權代表相鄰的可能性大小。這樣圖中所表示的最短路徑，就是對句子最好的解釋。由于最短路徑問題的廣泛應用，很多學者都對此進行了深入的研究，隨著研究成果的成熟化也是產(chǎn)生了一些經(jīng)典的算法。近年來，對最短路徑研究的熱度依然不減，并且時間復雜度也降得越來越低。從實際意義上講，沒有哪一種算法能夠適用于所有的網(wǎng)絡形式，并且在所有的網(wǎng)絡形式上具有很好的空間和時間復雜性。這些算法又具有各自的優(yōu)缺點。按照起點終點及路徑的數(shù)據(jù)和特征，最短路徑問題可分為五種類型：兩個節(jié)點間的最短路徑、所有節(jié)點的最短路徑、K則最短路徑、實時最短路徑和指定必經(jīng)點的最短路徑問題。在交通網(wǎng)絡的路徑分析中，單源最短路徑問題更具有普遍意義，其算法有很多種，其中采用貪心及啟發(fā)策略的Dijkstra算法是目前最完善的，這是荷蘭計算機科學教授EdgerW.Dijkstra(1930-2002)在1959年發(fā)現(xiàn)的一個算法，它以極強的抗差性得到普及和應用。再有就是由弗洛伊德（floyd）提出的另一個算法，又稱傳遞閉包方法，求每一對節(jié)點之間的最短路徑。本文就從上述幾類來分別介紹最短路徑的幾種常用算法，并介紹最短路徑問題中的算法改進。本文的其它部分組織如下：第一章概述了交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)的目的和意義、選題背景和技術線路。第二章介紹所要用到的技術原理。第三章介紹最短路徑問題的幾種算法。第四章交通咨詢系統(tǒng)的設計及實現(xiàn)。第五章為總結，提出文章的缺點與不足之處，談談自己的想法，并提出發(fā)展期望。一、緒論（一）課題的背景和意義現(xiàn)如今，我國的各大城市都有著交通擁堵、道路堵塞和交通事故的頻繁發(fā)生，這些都隨著城市私家車的不斷增加和城市汽車交通運輸?shù)募涌彀l(fā)展越來越困擾著我們的生活，并且汽車工業(yè)發(fā)展所引發(fā)的道路交通不能滿足實際需求的種種交通問題也越來越嚴重，越來越突出。為了解決這些問題，除了通常所用的解決辦法，譬如修建必要的道路交通網(wǎng)、針對交通事故多發(fā)路段、修建一系列的交通安全設施，這些設施包括道路信號機、道路標識、交通指揮中心等有助于交通安全的設施，來改善道路的交通環(huán)境，提高交通的順暢性，在一定程度上緩解交通擁擠狀況。而且在必要的時候能夠把道路、車輛、城市的發(fā)展需求等，大都與交通有關的基本因素歸為一體，在這些基本因素的基礎上，采用信息通信技術、信息自動采集技術、電子技術、網(wǎng)絡技術、自動控制以及其他的科學技術把它們聯(lián)系起來，開發(fā)一個可供模擬操作的城市交通管理系統(tǒng)。只有將這些方法結合起來，才能有效地解決隨著交通需求不斷增長、交通系統(tǒng)日益龐大復雜，所帶來的交通問題。隨著交通網(wǎng)絡越來越發(fā)達，人們在旅游、出差或者其他出行時，不僅會關心費用問題，而且對里程和所需要的時間等問題也特別感興趣。為了能夠更方便人們的出行，我們就應該以最短路徑問題建立一個交通咨詢系統(tǒng)。這樣的一個交通系統(tǒng)可以回答人們提出的有關交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。本題目的意義在于，用java軟件技術實現(xiàn)最短路徑算法在交通咨詢中的重要應用，對模擬結果進行分析討論，為將來能夠有效解決各大城市的交通問題提供可靠的依據(jù)。（二）研究現(xiàn)狀本節(jié)闡述三方面問題，首先簡要回顧最短路徑算法研究現(xiàn)狀，然后概要總結最短路徑算法分類，最后簡單論述最短路徑算法的時間復雜度。1.最短路徑算法研究現(xiàn)狀最短路徑問題一直是計算機科學、運籌學、地理信息科學等學科領域的研究熱點。國內(nèi)外大量專家學者對此問題進行了深入研究。經(jīng)典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結構及算法的有效結合使得新的最短路徑算法不斷涌現(xiàn)。常用的路徑規(guī)劃方法有:平行最短路徑搜索算法，蟻群算法，基于矩陣負載平衡的啟發(fā)算法,EBSP*算法和Dijkstra算法等。創(chuàng)門在空間復雜度、時間復雜度、易實現(xiàn)性及應用范圍等方面各具特色但是因為Dijkstra算法可以給出最可靠的最短路徑，并且容易實現(xiàn)，所以備受青睞和并被廣泛應用。經(jīng)典的Dijkstra算法的時間復雜度為，直接應用到大規(guī)模城市路網(wǎng)時，最短路徑查詢時間難以令人接受，專家學者紛紛開展Dijkstra優(yōu)化算法研究，概括起來，以往研究者主要是從5個方面對最短路徑算法進行性能優(yōu)化：(1)基于數(shù)據(jù)存儲結構的優(yōu)化，以空間換取時間；(2)基于路網(wǎng)規(guī)?？刂频膬?yōu)化；(3)基于搜索策略的優(yōu)化；(4)優(yōu)先級隊列結構的優(yōu)化；(5)基于雙向搜索的并行計算優(yōu)化。本文所研究的算法內(nèi)容融合了除(4)之外的所有優(yōu)化策略，首先采用堆數(shù)據(jù)結構將Dijkstra算法時間復雜度降至O(NlogN)，然后采用橢圓限制算法搜索區(qū)域，控制搜索規(guī)模，限定搜索方向，最后在本文提出的二樹算法中運用了并行運算思想，極大地降低了最短路徑查詢時間。2.最短路徑算法分類由于問題類型、網(wǎng)絡特性的不同，最短路徑算法也表現(xiàn)出多樣性。按照最短路徑問題分類，最短路徑問題通?？煞譃?個基本類型：一是單源最短路徑問題，即查找某一源點到其余各點的最短路徑；另一類是查找某個節(jié)點對之間的最短路徑。最短路徑問題具體可細分為以下幾種，單源最短路徑問題，單對節(jié)點間最短路徑、所有節(jié)點間最短路徑、k則最短路徑、實時最短路徑、指定必經(jīng)節(jié)點的最短路徑以及前N條最短路徑問題等，本文的研究范疇屬于單對節(jié)點間最短路徑問題。按照網(wǎng)絡類型和表示方法分類，網(wǎng)絡可以分為稀疏網(wǎng)絡和非稀疏網(wǎng)絡，常用的表示方法有鄰接矩陣和鄰接表。鄰接矩陣方法能夠在o(i)時間內(nèi)查詢到任意兩個節(jié)點之間是否有一條邊，它的空間復雜度為?，F(xiàn)實生活中網(wǎng)絡節(jié)點往往很多，動輒上萬，而且是稀疏網(wǎng)絡居多，比如城市路網(wǎng)，所以用鄰接矩陣表示既不現(xiàn)實，又浪費空間。鄰接表是另一種存儲網(wǎng)絡拓撲的數(shù)據(jù)結構，它是一種鏈式存儲結構，對于交通網(wǎng)絡等稀疏圖，采用鄰接表數(shù)據(jù)結構存儲網(wǎng)絡拓撲數(shù)據(jù)空間復雜度僅為O(M十N)，不存在存儲空間的浪費。鄰接表數(shù)據(jù)結構已被證明是網(wǎng)絡表達中最有效率的數(shù)據(jù)結構，在最短路徑算法中得到了廣泛應用。3.算法時間復雜度Dijkstra算法最簡單的實現(xiàn)方法是用一個鏈表或者數(shù)組來存儲所有頂點的集合，此時算法的時間復雜度是.對于邊數(shù)M遠少于的稀疏圖來說，為節(jié)省存儲空間，可以用鄰接表更有效的實現(xiàn)該算法;為縮短算法查詢時間，可以將一個二叉堆或者斐波納契堆用作優(yōu)先隊列來尋找最小的頂點。當用到二叉堆的時候，算法所需的時間為O((M+N)logN);當用斐波納契堆時，算法時間復雜度為O(M+N1ogN)。對于城市路網(wǎng)，由于N/M介于1.5和2之間所以采用堆數(shù)據(jù)結構，Dijkstra算法時間復雜度為O(NlogN)。（三）研究內(nèi)容本文的研究范疇是智能交通系統(tǒng)中的最短路徑算法，研究領域是城市路網(wǎng)中的限制搜索區(qū)域最短路徑算法，研究內(nèi)容是典型城市路網(wǎng)中最短路徑算法的理論研究及實驗驗證，研究目的是保證查詢結果可靠的情況下，最大程度降低最短路徑查詢時間，研究方法是充分研究和利用城市路網(wǎng)的特征參數(shù)，降低最短路徑算法冗余度和復雜度，性能驗證是軟件仿真預測和實測數(shù)據(jù)統(tǒng)計雙重評估標準。（四）論文結構論文共分為六個章節(jié)，各章內(nèi)容組織如下:第一章為緒論，首先敘述了本課題研究的背景意義，然后依次回顧了智能交通系統(tǒng)的發(fā)展歷程，介紹了最短路徑算法的研究現(xiàn)狀，最終引出論文的工作內(nèi)容并給出了論文組織結構。第二章是本文的理論研究基礎，介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，著重討論了Dijkstra算法、Floyd算法的運行機理。第三章是介紹了系統(tǒng)的開發(fā)工具及系統(tǒng)的運行環(huán)境。第四章分析交通咨詢系統(tǒng)的最短路徑算法實現(xiàn)代碼的編寫。第五章簡要介紹了系統(tǒng)的界面設計。第六章總結，提出文章的缺點與不足之處，談談自己的想法，并提出發(fā)展期望。二、最短路徑算法相關原理本章介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，重點討論Dijkstra算法、Floyd算法的實現(xiàn)原理。（一）Dijkstra算法Dijkstra算法是一個按權值大小遞增的次序產(chǎn)生最優(yōu)路徑的算法，用于計算從有向圖中任意結點到其他結點的最優(yōu)路徑。設一個有向圖G=(V,E),已知各邊的權值，以某指定點為源點，求到圖的其余各點的最短路徑。1.算法思想分析1959年狄克斯特拉（Dijkstra）提出一個按路徑“長度”遞增的次序產(chǎn)生最短路徑的算法，即：把圖中所有的頂點分成兩組，第一組S包括已經(jīng)確定最短路徑的頂點，初始時只含有源點；第二組V-S中包括尚未包括最短路徑的頂點，初始時含有圖中初源點之外的所有其他頂點。按路徑長度遞增的順序計算源點到各頂點的最短路徑，逐個把第二組中的頂點加到第一組中去，直至V=S。2.實現(xiàn)思路有向網(wǎng)用鄰接矩陣cost[][]表示，其中規(guī)定：（1）如果兩個頂點之間無直接路徑，即弧對應權值為無窮大；（2）兩個頂點之間有直接路徑的，矩陣中的權值就是弧對應的公路長度；（3）對應的值為0。S集合初始存放最短路徑的源點，計算過程中將已經(jīng)確定了最短路徑的頂點加到S中去。Dist數(shù)組最終存放源點到各頂點的最短路徑結果。Path數(shù)組最終存放源點到個頂點的最短路徑經(jīng)過的頂點。3.計算步驟如下圖所示：由F到A的路徑有三條：FA：24；FBA：5+18=23；FBCA：5+7+9=21第一條最短路徑為與源點V鄰接頂點的弧集合中，權值最小的弧。下一條長度次短的最短路徑是：假設該次短路徑的終點是，則這條路徑或者是，或者是，它的長度或者是從V到弧上的權值，或者是V到路徑長度與到的弧上權值之和。引進一個輔助向量D，它的每個分量D[i]表示當前找到的從源點V到每個終點的最短路徑的長度。設用帶權的鄰接矩陣dist[i][j]來表示有向圖，dist[i][j]表示弧上的權值，若不存在，則置dist[i][j]為某一最大值。向量S為已找到從V出發(fā)的最短路徑的終點的集合，其初始值為空集。算法按下面的步驟進行：①從V出發(fā)到圖上其余各個頂點（終點）可能達到的最短路徑長度的初始值為：D[i]=dist[ORDINAL(V)][i]，Vi∈V其中ORDINAL(V)表示頂點V在有向圖中的序號②選擇Vj，使D[j]=Min{D[i]|ViS，Vi∈V}Vj就是當前求得的一條從V出發(fā)的最短路徑的終點，且令S=S∪{j}即將j加入到S集合中。③修改從V出發(fā)到集合V-S上所有頂點Vk可達到的最短路徑長度。如果D[j]+dist[j][k]<D[k]則修改D[k]為D[k]=D[j]+dist[j][k]④重復操作（2），（3）共n-1次。最后求得從V到圖上其余各定點的最短路徑是依路徑長度遞增的序列。例：對上圖，鄰接矩陣為最短路徑求解過程圖例，F(xiàn)為源點；初始狀態(tài)，ABCDEF100000S1000000∞25∞524D0∞25∞524無無FD無FBFA無無FD無FBFA求得min{D}={24,5,∞,25,∞}=5，最短路徑FB②以D[j]修改（即FB路徑長度修改）向量D，ABCDEF100010S1000100∞25125230∞2512523FBAFBFBC無無FBAFBFBC無無FD求得min{D}={23,12,25,∞}=12，最短路徑FBC③以D[j]修改（即FBC路徑長度修改）向量D，ABCDEF100110S1001100∞25125210∞2512521FBCAFBFBC無無FBCAFBFBC無無FD求得min{D}={21,25,∞}=21，最短路徑FBCA④以D[j]修改（即FBCA路徑長度修改）向量D，ABCDEF100111S1001110∞2512521D0∞2512521FBCAFBFBC無無FDFBCAFBFBC無無FD求得min{D}={25,∞}=25，最短路徑FD⑤以D[j]修改（即FD路徑長度修改）向量D，ABCDEF101111S1011110∞2512521D0∞2512521FBCAFBFBC無無FDFBCAFBFBC無無FD求得min{D}={∞}=∞，即FE無路徑（二）Floyd算法Floyd-Warshall算法（Floyd-Warshallalgorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復雜度為O(N3)，空間復雜度為O(N2)。1.算法思想原理：Floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為這個目標重新做一個詮釋（這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在）從任意節(jié)點i到任意節(jié)點j的最短路徑不外乎2種可能，1是直接從i到j，2是從i經(jīng)過若干個節(jié)點k到j。所以，我們假設Dis(i,j)為節(jié)點u到節(jié)點v的最短路徑的距離，對于每一個節(jié)點k，我們檢查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，我們便設置Dis(i,j)=Dis(i,k)+Dis(k,j)，這樣一來，當我們遍歷完所有節(jié)點k，Dis(i,j)中記錄的便是i到j的最短路徑的距離。2.算法描述：a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。b.對于每一對頂點u和v，看看是否存在一個頂點w使得從u到w再到v比己知的路徑更短。如果是更新它。3.Floyd算法過程矩陣的計算十字交叉法方法：兩條線，從左上角開始計算一直到右下角如下所示給出矩陣，其中矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點之間最短路徑所必須經(jīng)過的點相應計算方法如下：最后A3即為所求結果。三、開發(fā)工具與環(huán)境（一）Java技術1.Java簡介Java是由SunMicrosystems公司于1995年5月推出的Java程序設計語言（以下簡稱Java語言）和Java平臺的總稱。用Java實現(xiàn)的HotJava瀏覽器（支持Javaapplet）顯示了Java的魅力：跨平臺、動感的Web、Internet計算。從此，Java被廣泛接受并推動了Web的迅速發(fā)展，常用的瀏覽器現(xiàn)在均支持Javaapplet。另一方面，Java技術也不斷更新。

Java平臺由Java虛擬機（JavaVirtualMachine）和Java應用編程接口（ApplicationProgrammingInterface、簡稱API）構成。Java應用編程接口為Java應用提供了一個獨立于操作系統(tǒng)的標準接口，可分為基本部分和擴展部分。在硬件或操作系統(tǒng)平臺上安裝一個Java平臺之后，Java應用程序就可運行?，F(xiàn)在Java平臺已經(jīng)嵌入了幾乎所有的操作系統(tǒng)。這樣Java程序可以只編譯一次，就可以在各種系統(tǒng)中運行。Java應用編程接口已經(jīng)從1.1x版發(fā)展到1.2版。目前常用的Java平臺基于Java1.4，最近版本為Java1.6。

Java分為三個體系JavaSE，JavaEE，JavaME。Java的特點是：(1)Java的簡單性：和C++相比，語法簡單了，取消了指針的語法；內(nèi)存分配和回收不需要我們來過渡關注，C++可以多繼承，但java只能是單繼承，相對于類來說。（注：接口可以多繼承）使用Asp可以組合HTML頁、腳本命令和ActiveX組件以創(chuàng)建交互的Web頁和基于Web的功能強大的應用程序。(2)java面向對象：java算是純面向對象，但jquery是更純的面向對象。在java編程思想這本書說過，“Everythingisobject!”這樣便于人類的構思和設計，更符合人們的思考問題方式。(3)分布式：主要還是用在EJB上。(4)安全性：java的語法限定了源程序的安全性，首先編譯器會進行源代碼的第一步檢查。(5)跨平臺：java能夠跨越不同的操作系統(tǒng)平臺，平臺無關性怎么跨平臺呢？主要是在不同的操作系統(tǒng)中，JVM規(guī)范都是一樣的，被JVM加載成各個操作系統(tǒng)所支持的，屏蔽了底層操作系統(tǒng)的差異。(6)高性能：開閉原則對擴展開放，對修改關閉java是即時編譯的。(7)多線程。2.Java的處理流程(1)首先編輯.java源程序。(2)編譯成.class字節(jié)碼文件bytecode（一種二進制文件）。(3)最后被java虛擬機（JVM）加載解釋并執(zhí)行。四、交通咨詢系統(tǒng)的實現(xiàn)（一）系統(tǒng)分析為了保證系統(tǒng)能夠長期、安全、穩(wěn)定、可靠、高效的運行，系統(tǒng)應該滿足以下的性能需求：統(tǒng)一處理的準確性和及時性：系統(tǒng)處理的準確性和及時性是系統(tǒng)的必要性能。在系統(tǒng)設計和開發(fā)過程中，要充分考慮系統(tǒng)當前和將來可能承受的工作量，使系統(tǒng)的處理能力和響應時間能夠滿足企業(yè)對員工信息處理的需求。系統(tǒng)的開放性和可擴充性：系統(tǒng)在開發(fā)過程中，應該充分考慮以后的可擴充性。例如數(shù)據(jù)表中用戶選擇字段方式的改變，用戶查詢的需求也會不斷的更新和完善。所有這些，都要求系統(tǒng)提供足夠的手段進行功能的調整和擴充。而要實現(xiàn)這一點，應通過系統(tǒng)的開放性來完成，既系統(tǒng)應是一個開放系統(tǒng)，只要符合一定的規(guī)范，可以簡單的加入和減少系統(tǒng)的模塊，配置系統(tǒng)的硬件。通過軟件的修補、替換完成系統(tǒng)的升級和更新?lián)Q代。系統(tǒng)的易用性和易維護性：要實現(xiàn)這一點，就要求系統(tǒng)應該盡量使用用戶熟悉的術語和中文信息的界面；針對用戶可能出現(xiàn)的使用問題，要提供足夠的在線幫助，縮短用戶對系統(tǒng)熟悉的過程。系統(tǒng)的數(shù)據(jù)要求：(1)數(shù)據(jù)錄入和處理的準確性和實時性；(2)數(shù)據(jù)的一致性與完整性；(3)數(shù)據(jù)的共享與獨立性。1.系統(tǒng)的設計內(nèi)容： 設計一個交通咨詢系統(tǒng)，能讓旅客咨詢?nèi)我庖粋€城市到另一個城市之間的最短路徑問題。 該交通咨詢系統(tǒng)設計共三部分，一是建立交通網(wǎng)絡圖的存儲結構；二是解決單源路徑問題；最后再實現(xiàn)兩個城市之間的最短路徑問題。2.系統(tǒng)的設計思想用鄰接矩陣來存儲交通網(wǎng)絡圖的信息，運用迪杰斯特拉算法實現(xiàn)圖上單源最短路徑問題，然后運用費洛伊德算法實現(xiàn)圖中任意一對頂點間最短路徑問題，這樣就會實現(xiàn)旅客所要咨詢的問題。3.系統(tǒng)設計流程該交通咨詢系統(tǒng)要完成城市網(wǎng)絡圖的存儲，并要實現(xiàn)求任意一個城市頂點到其他城市頂點的最短路徑問題，還要實現(xiàn)任意兩個城市頂點間的最短路徑問題。故設計要分成三部分，一是建立網(wǎng)絡交通的存儲結構，二是解決單源最短路徑問題；最后時限兩個城市之間的最短路徑問題。（二）系統(tǒng)功能結構1.系統(tǒng)構架設計 首先總體的步驟是： 迪克斯特拉算法的具體流程圖如下：弗洛伊德算法的具體流程圖如下：2.系統(tǒng)詳細設計程序源代碼如下：//Floyd算法publicclassShortPathALG{ privateDrawing[]circleList=null;//用于存放結點 privateDrawing[]lineList=null;//用于存放線段 privateintmGraph[][]=null;//用于存儲圖的鄰接矩陣 privateintmGraphCopy[][]=null; privateStringdis="";//最短路徑結果 privateStringdrawLineRed="";//要繪制的紅線路徑 privateintcircleNum=0;//結點的個數(shù) privateintlineNum=0;//線段的個數(shù) privateDrawJPaneldrawJPanel=null; publicShortPathALG(DrawJPaneldraw){ drawJPanel=draw; //TODO最短路徑的算法初始化結點和線 circleList=drawJPanel.getCircleList();//獲得結點對象數(shù)組 lineList=drawJPanel.getLineList();//獲得線段對象數(shù)組 circleNum=drawJPanel.getCircleCount();//獲得結點的個數(shù) lineNum=drawJPanel.getLineCount(); mGraph=newint[circleNum][circleNum];//為鄰接矩陣分配空間0行、0列不用 for(inti=0;i<circleNum;i++){//初始化鄰接矩陣全賦值為-1（距離不可能是負數(shù)） for(intj=0;j<circleNum;j++){ if(i==j) mGraph[i][j]=0; else{ mGraph[i][j]=32767; } } } changeLineColor();//初始化線條的顏色 mGraphInitialize();//初始化鄰接矩陣 path_FLOYD(getmGraphCopy()); } //初始化線條的顏色 privatevoidchangeLineColor(){ for(inti=1;i<lineNum;i++){ lineList[i].setColor(Color.blue); } drawJPanel.repaint(); } //初始化鄰接矩陣 publicvoidmGraphInitialize(){ for(inti=1;i<lineNum;i++){//循環(huán)遍歷線條的起點與終點 intm=32767; try{ m=Integer.parseInt(lineList[i].name);//如果輸入的距離不能轉換成整形默認距離是1 }catch(Exceptione){ m=1; } //構建無向圖 if(lineList[i].name.equals("")) m=1; mGraph[lineList[i].xLocation][lineList[i].yLocation]=m; mGraph[lineList[i].yLocation][lineList[i].xLocation]=m; } } //輸出鄰接矩陣 publicvoidshowMGraph(){ Strings="最短路徑的鄰接矩陣是(無向圖)：\n"; for(inti=1;i<circleNum;i++){ if(!circleList[i].name.equals("")){ s=s+circleList[i].name+""; }else{ s=s+i+""; } } s=s+"\n"; for(inti=1;i<circleNum;i++){ for(intj=1;j<circleNum;j++){ s=s+mGraph[i][j]+""; } s=s+"\n"; } s=dis; lineColor();//修改路徑的顏色 JOptionPane.showMessageDialog(drawJPanel,s,"最短路徑", JOptionPane.PLAIN_MESSAGE); } //修改路徑的顏色 privatevoidlineColor(){//修改路徑的顏色 intgv[];//存放線段頂點 inti=1; StringTokenizertokenizer=newStringTokenizer(drawLineRed,"-->"); gv=newint[tokenizer.countTokens()+1];//動態(tài)的決定數(shù)組的長度 while(tokenizer.hasMoreTokens()){ Stringd=tokenizer.nextToken(); gv[i]=Integer.valueOf(d);//將字符串轉換為整型 i++; } for(intj=1;j<gv.length-1;j++){ for(i=1;i<lineNum;i++){ booleanx=lineList[i].xLocation==gv[j] &&lineList[i].yLocation==gv[j+1]; booleany=lineList[i].yLocation==gv[j] &&lineList[i].xLocation==gv[j+1]; if(x||y){ lineList[i].setColor(Color.red); } } } drawJPanel.repaint(); } //最短路徑算法FLOYD算法 intD[][]=null;//D存放每對頂點之間的最短路徑值 intpath[][]=null;//p存放每對頂點之間的最短路徑 intlength=0; publicvoidpath_FLOYD(intdata[][]){ inti,j,k; length=data.length; D=newint[length][length];//D存放每對頂點之間的最短路徑值 path=newint[length][length];//p存放每對頂點之間的最短路徑 for(i=1;i<length;i++){//各節(jié)點之間的初始已知路徑及距離 for(j=1;j<length;j++){ D[i][j]=data[i][j];// path[i][j]=-1; } }//for for(k=1;k<length;k++){ for(i=1;i<length;i++){ for(j=1;j<length;j++){ if(i==j)//對角線上的元素（即頂點自身之間）不予考慮 continue; if(D[i][k]+D[k][j]<D[i][j]){//從i經(jīng)k到j的一條路徑更短 D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } } } } publicvoidpath_DIJKSTRA(intdata[][]){ inti,j,k; length=data.length; D=newint[length][length];//D存放每對頂點之間的最短路徑值 path=newint[length][length];//p存放每對頂點之間的最短路徑 for(i=1;i<length;i++){//各節(jié)點之間的初始已知路徑及距離 for(inty=2;y<=data.length;y++){ if(table[1][y]>0)//如果y相鄰于1 L.set(y,length(1,y)); else L.set(y,Integer.MAX_VALUE); } for(intj=1;j<=V.size()-1;j++){ inty=findTheMinInL(); X.add(y); Y.remove(y); for(intjj=1;jj<table.length;jj++){ if(table[y][jj]>0) if(Y.contains(jj) &&((L.get(y)+length(y,jj))<L.get(jj))) L.set(jj,L.get(y)+length(y,jj)); } } inti,j,k; length=data.length; D=newint[length][length];//D存放每對頂點之間的最短路徑值 path=newint[length][length];//p存放每對頂點之間的最短路徑 for(i=1;i<length;i++){//各節(jié)點之間的初始已知路徑及距離 for(j=1;j<length;j++){ D[i][j]=data[i][j];// path[i][j]=-1; } }//for for(k=1;k<length;k++){ for(i=1;i<length;i++){ for(j=1;j<length;j++){ if(i==j)//對角線上的元素（即頂點自身之間）不予考慮 continue; if(D[i][k]+D[k][j]<D[i][j]){//從i經(jīng)k到j的一條路徑更短 D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } } } } //最短路徑輸出 publicStringdisPath(inti,intj){ //TODOAuto-generatedmethodstub booleanc1Name=!circleList[i].name.equals(""); booleanc2Name=!circleList[j].name.equals(""); if(D[i][j]==32767){ if(i!=j){ if(c1Name){ dis="從"+circleList[i].name+"到"; }else{ dis="從"+i+"到"; } if(c2Name){ dis+=circleList[j].name+"沒有路徑\n"; }else{ dis+=j+"沒有路徑\n"; } } }else{ if(c1Name){ dis="從"+circleList[i].name+"到"; }else dis="從"+i+"到"; if(c2Name){ dis+=circleList[j].name+"路徑為:"; }else dis+=j+"路徑為:"; if(c1Name){ dis+=circleList[i].name+"-->"; }else dis+=i+"-->"; if(c2Name){ dis+=ppath(i,j)+circleList[j].name+"\n路徑長度為:" +D[i][j] +"\n"; }else{ dis+=ppath(i,j)+j+"\n路徑長度為:"+D[i][j]+"\n"; } drawLineRed=i+"-->"+lineString+j; } returndis; } Strings="";//存放路徑 StringlineString="";//劃紅線的路徑 privateStringppath(inti,intj){ intk; k=path[i][j]; if(k==-1) returns; ppath(i,k); if(!circleList[k].name.equals("")){ s=s+circleList[k].name+"-->"; }else{ s=s+k+"-->"; } lineString+=k+"-->"; ppath(k,j); returns; } //得到鄰接矩陣對象的副本 publicint[][]getmGraphCopy(){ mGraphCopy=newint[mGraph.length][mGraph.length]; for(inti=0;i<mGraph.length;i++) for(intj=0;j<mGraph.length;j++) mGraphCopy[i][j]=mGraph[i][j]; returnmGraphCopy; }}//Dijkstra算法packageTest;importjava.util.TreeMap;importjava.util.ArrayList;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.io.IOException;classPoint{ privateintid;//點的id privatebooleanflag=false;//標志是否被遍歷 intsum;//記錄總的點個數(shù) privateTreeMap<Integer,Integer>thisPointMap=newTreeMap<Integer,Integer>();//該點到各點的距離。 BufferedReaderbufr=newBufferedReader(newInputStreamReader(System.in)); Point(intsum){//構造函數(shù)帶有頂點個數(shù) this.sum=sum; } publicvoidsetId(intid){//設置頂點id this.id=id; } publicintgetId(){//獲得頂點id returnthis.id; } publicvoidchangeFlag(){//修改訪問狀態(tài)。 this.flag=true; } publicbooleanisVisit(){//查看訪問狀態(tài) returnflag; } publicvoidsetLenToOther()throwsIOException{//初始化改點到各頂點的距離。 System.out.println("=======請輸入頂點"+(this.id+1)+"至其他各頂點的邊距======="); for(inti=0;i<sum;i++){ if(i==this.id) thisPointMap.put(this.id,0); else{ System.out.print("至頂點"+(i+1)+"的距離："); booleanflag=true; intlen=0; while(flag){ try{ len=Integer.valueOf(bufr.readLine()); flag=false; }catch(NumberFormatExceptione){ System.out.print("輸入有誤，請重新輸入："); } }; thisPointMap.put(i,len); } } } //該點到頂尖id的距離。 publicintlenToPointId(intid){ returnthisPointMap.get(id); }}classDijkstra{ publicstaticvoidmain(String[]args)throwsIOException{ ArrayList<Point>point_arr=newArrayList<Point>();//存儲點集合 BufferedReaderbufr=newBufferedReader(newInputStreamReader(System.in)); System.out.print("請輸入頂點個數(shù)："); intsum=0; booleanflag=true; while(flag){ try{ sum=Integer.valueOf(bufr.readLine()); flag=false; }catch(NumberFormatExceptione){ System.out.print("輸入有誤，請重新輸入："); } }; for(inti=0;i<sum;i++){//初始化 Pointp=newPoint(sum); p.setId(i); p.setLenToOther(); point_arr.add(p); } System.out.print("請輸入起始頂點id："); booleanflag2=true; intstart=0; while(flag2){ try{ start=Integer.valueOf(bufr.readLine())-1; if(start>sum-1||start<0) thrownewNumberFormatException(); flag2=false; }catch(NumberFormatExceptione){ System.out.print("輸入有誤，請重新輸入："); } }; showDijkstra(point_arr,start);//單源最短路徑遍歷 } publicstaticvoidshowDijkstra(ArrayList<Point>arr,inti){ System.out.print("頂點"+(i+1)); arr.get(i).changeFlag(); Pointp1=getTopointMin(arr,arr.get(i)); if(p1==null) return; intid=p1.getId(); showDijkstra(arr,id); } publicstaticPointgetTopointMin(ArrayList<Point>arr,Pointp){ Pointtemp=null; intminLen=Integer.MAX_VALUE; for(inti=0;i<arr.size();i++){ //當已訪問或者是自身或者無該路徑時跳過。 if(arr.get(i).isVisit()||arr.get(i).getId()==p.getId()||p.lenToPointId(i)<0) continue; else{ if(p.lenToPointId(i)<minLen){ minLen=p.lenToPointId(i); temp=arr.get(i); } } } if(temp==null) returntemp; else System.out.print("@--"+minLen+"-->"); returntemp; }}3.測試數(shù)據(jù)及分析 Floyd算法輸出結果分析如下： Dijkstra算法運行結果如下：五、設計總結 城市現(xiàn)代化的目的，說到底是為了人的現(xiàn)代化。交通咨詢現(xiàn)代化作為城市現(xiàn)代化的重要內(nèi)容，首先應是城市居民的生活交通現(xiàn)代化，這是以人為本原則的基本含義和根本要求。一般來說，實現(xiàn)居民生活交通現(xiàn)代化（主要是交通咨詢的現(xiàn)代化）便可以滿足城市生產(chǎn)和經(jīng)營交通現(xiàn)代化的要求。交通咨詢系統(tǒng)服務于城市現(xiàn)代化發(fā)展戰(zhàn)略，以建設現(xiàn)代化交通為目標，堅持以人為本原則，優(yōu)化交通結構，大力發(fā)展公共交通。 本次設計只是實現(xiàn)了兩點之間最短路徑可行距離的查詢，而在現(xiàn)實生活中我們不僅要考慮兩點之間的最短距離，還要考慮轉車次數(shù)，這正是本次設計的不足之處。調查表明人們在出行時往往更傾向于轉車次數(shù)較少的路線，這樣便降低了人們的辦事效率。因此，完善的交通咨詢系統(tǒng)對兩點之間的最短路徑的查詢應以轉車次數(shù)少為條件。 現(xiàn)實世界的交通網(wǎng)絡是復雜的，僅僅考慮道路網(wǎng)的時間損耗和長度分析很難滿足實際需要，尤其是在城市交通網(wǎng)絡中，在不久的將來，本系統(tǒng)還將致力于通過分析城市道路狀況，交通管理設施，交通結構及管理狀況，考慮道路的進行和單行問題，排除阻礙交通的不通路，給出兩點之間的最優(yōu)路徑。致謝時間過得很快，一轉眼四年的大學時間已近結尾，在這四年的生活學習中，許多老師和同學給予了我很多幫助。在這幾個月的畢業(yè)設計中，老師和同學們給予了我很大的幫助，因此我非常感謝他們，感謝他們這么長時間的陪伴與幫助。在這里我最想感謝的人就是指導老師。在畢業(yè)設計期間，指導老師的悉心教導深刻地印在我心里，她平易近人，知識淵博，又對我們嚴格要求和嚴厲督促，這時的我在即將離開大學之際又多了一份很美好的回憶，也增加了自身的知識寬度。當然還要感學院各位老師對我的培養(yǎng)和關心，是他們?yōu)槲覄?chuàng)造了良好的學習環(huán)境。感謝我的同學和朋友對我在生活和學習上的無私幫助，感謝他們給我?guī)砻恳惶斓臍g笑。感謝每位同學在論文寫作期間的大力支持與鼓勵。我將最誠摯的感謝獻給我的父母，我今天的成績也凝聚了他們辛勤的汗水。正是因為父母對我的關心、教誨和鼓勵使我能夠好好地完成學業(yè)，并向更高的目標奮斗。參考文獻[1]嚴蔚敏。數(shù)據(jù)結構（C語言版）[M].北京，清華大學出版社，1997.[2]王海英，黃強，李傳濤。圖論算法及其MATLAB實現(xiàn)[M].北京，北京航空航天大學出版社，2010.[3]周先曙。最短路徑問題及其解法研究[J],電腦知識與技術，2010，（06）.[4]王朝瑞。圖論[M].北京，北京理工大學出版社，1997.[5]陸鋒。最短路徑算法：分類體系與研究進展[J].測繪學報，2001，（3）：269-275[6]陳簫楓，蔡秀云，唐德強。最短路徑算法分析及其在公交查詢的應用[J].工程圖學學報，2001，（3）[7]宋曉宇，于瀾洋，孫煥良，許景科。交通網(wǎng)絡中出現(xiàn)阻塞路徑情況下增量路徑查找算法[J].沈陽建筑大學學報（自然科學版），2009，（4）[8]張池軍，楊永健，趙洪波。基于路徑依賴的最短路徑算法的改進與實現(xiàn)[J].計算機工程與應用，2006，(25)[9]賀喜玲，季煥淑。最短路徑算法[J].大科技（科技天地），2011，(6)[10]李擎，謝四江，童新海，王志良。一種用于車輛最短路徑規(guī)劃的自適應遺傳算法及其與Dijkstra和A^＊算法的比較[J].北京科技大學學報,2006,(11):1082-1086基于C8051F單片機直流電動機反饋控制系統(tǒng)的設計與研究基于單片機的嵌入式Web服務器的研究MOTOROLA單片機MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機溫度控制系統(tǒng)的研制基于MCS-51系列單片機的通用控制模塊的研究基于單片機實現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調節(jié)器單片機控制的二級倒立擺系統(tǒng)的研究基于增強型51系列單片機的TCP/IP協(xié)議棧的實現(xiàn)基于單片機的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機系統(tǒng)的圖像采集與處理技術的研究基于單片機的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機的交流伺服電機運動控制系統(tǒng)研究與開發(fā)基于單片機的泵管內(nèi)壁硬度測試儀的研制基于單片機的自動找平控制系統(tǒng)研究基于C8051F040單片機的嵌入式系統(tǒng)開發(fā)基于單片機的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機實現(xiàn)一種基于單片機的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機的在線間歇式濁度儀的研制基于單片機的噴油泵試驗臺控制器的研制HYPERL