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

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

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

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

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

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

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