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

1、<p>　　本科畢業(yè)論文(設(shè)計)</p><p>　　論文題目： 交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn) </p><p>　　學(xué)生姓名： </p><p>　　學(xué) 號： </p>

2、<p>　　專 業(yè)： 信息管理與信息系統(tǒng) </p><p>　　班 級： </p><p>　　指導(dǎo)教師： </p><p>　　完成日期： 2015年 5月 5日</p><p><b>　　目錄</b></p>

3、<p><b>　　序 言1</b></p><p><b>　　一、緒 論2</b></p><p>　?。ㄒ唬┱n題的背景和意義2</p><p><b>　?。ǘ┭芯楷F(xiàn)狀2</b></p><p>　　1.最短路徑算法研究現(xiàn)狀2</p>

4、<p>　　2.最短路徑算法分類3</p><p>　　3.算法時間復(fù)雜度3</p><p><b>　?。ㄈ┭芯績?nèi)容4</b></p><p><b>　?。ㄋ模┱撐慕Y(jié)構(gòu)4</b></p><p>　　二、最短路徑算法相關(guān)原理4</p><p>　

5、?。ㄒ唬〥ijkstra算法4</p><p>　　1.算法思想分析5</p><p><b>　　2.實現(xiàn)思路5</b></p><p><b>　　3.計算步驟5</b></p><p>　　（二）Floyd算法7</p><p>　　1.算法思想原理：8&l

6、t;/p><p><b>　　2.算法描述：8</b></p><p>　　3.Floyd算法過程矩陣的計算----十字交叉法8</p><p>　　三、開發(fā)工具與環(huán)境10</p><p>　?。ㄒ唬㎎ava技術(shù)10</p><p>　　1. Java簡介10</p><

7、p>　　2.Java的處理流程11</p><p>　　四、交通咨詢系統(tǒng)的實現(xiàn)11</p><p>　?。ㄒ唬┫到y(tǒng)分析11</p><p>　　1.系統(tǒng)的設(shè)計內(nèi)容：11</p><p>　　2.系統(tǒng)的設(shè)計思想12</p><p>　　3.系統(tǒng)設(shè)計流程12</p><p>　?。?/p>

8、二）系統(tǒng)功能結(jié)構(gòu)12</p><p>　　1. 系統(tǒng)構(gòu)架設(shè)計12</p><p>　　2.系統(tǒng)詳細(xì)設(shè)計14</p><p>　　3. 測試數(shù)據(jù)及分析26</p><p><b>　　五、設(shè)計總結(jié)28</b></p><p><b>　　致謝29</b></p

9、><p>　　參 考 文 獻(xiàn)29</p><p>　　交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)</p><p><b>　　內(nèi) 容 摘 要</b></p><p>　　目前在交通咨詢領(lǐng)域，最短路徑算法的研究和應(yīng)用越來越多，其中最短路徑算法的效率問題是普遍關(guān)注并且在實際應(yīng)用中迫切需要解決的問題。</p><p&g

10、t;　　隨著現(xiàn)代生活節(jié)奏的加快，以及城市汽車數(shù)量的不斷增加，交通網(wǎng)絡(luò)也越來越發(fā)達(dá)，在交通工具和交通方式不斷更新的今天，人們在旅游、出差或者其他出行時，不僅會關(guān)心費用問題，而且對里程和所需要的時間等問題也特別感興趣。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問題建立一個交通咨詢系統(tǒng)。這樣的一個交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。</p>

11、<p>　　本文通過對幾個常見的最短路徑算法的分析，研究和實現(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)的合理的解決方案。</p><p>

12、;　　關(guān)鍵詞：交通咨詢 最短路徑 Dijkstra算法 Floyd算法</p><p>　　Shortest path algorithm of the Transport Advisory System Design and Implementation</p><p><b>　　Abstract</b></p><p>　　C

13、urrently in the field of traffic advisory, research and application of the shortest path algorithm become more and more, where in the efficiency of the shortest path algorithm is a common concern and in practice is an ur

14、gent need to solve the problem.</p><p>　　With the pace of modern life accelerate, as well as the increasing number of city car, transportation networks is more developed, in vehicles and transportation const

15、antly 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 t

16、o travel, we should build a shortest path problem traffic advisory system. Such a transportation system can answer</p><p>　　Through the analysis of several common shortest path algorithm research and realize

17、d that the classical Dijkstra algorithm, Floyd algorithm. We discussed various algorithms ideology, theory, implementation, data structures, as well as algorithms described and analyzed to compare their advantages and sh

18、ortcomings, and the practicality of the complexity of the specific time and space. For present characteristics of modern transportation network, classical shortest path algorithm analysis and resea</p><p>　　

19、Key words：traffic advisory shortest path Dijkstra algorithm Floyd algorithm</p><p><b>　　序 言</b></p><p>　　最短路徑問題一直在計算機(jī)科學(xué)、交通工程學(xué)、地理信息系統(tǒng)、運籌學(xué)等學(xué)科中是一個研究的熱點，它不僅是資源分配問題解決的基礎(chǔ)，更是線路選擇問題解決的

20、基礎(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)的最短路徑。在圖像分割問題中，最短路徑也有直接的

21、應(yīng)用：在語音識別中一個主要的問題就是識別同音詞，例如，to、two、too。為解決這個問題，我們需要建立一個圖，頂點代表可能的單詞，扁連接相鄰的單詞，邊上的權(quán)代表相鄰的可能性大小。這樣圖中所表示的最短路徑，就是對句子最好的解釋。</p><p>　　由于最短路徑問題的廣泛應(yīng)用，很多學(xué)者都對此進(jìn)行了深入的研究，隨著研究成果的成熟化也是產(chǎn)生了一些經(jīng)典的算法。近年來，對最短路徑研究的熱度依然不減，并且時間復(fù)雜度也降得越

22、來越低。從實際意義上講，沒有哪一種算法能夠適用于所有的網(wǎng)絡(luò)形式，并且在所有的網(wǎng)絡(luò)形式上具有很好的空間和時間復(fù)雜性。這些算法又具有各自的優(yōu)缺點。按照起點終點及路徑的數(shù)據(jù)和特征，最短路徑問題可分為五種類型：兩個節(jié)點間的最短路徑、所有節(jié)點的最短路徑、K則最短路徑、實時最短路徑和指定必經(jīng)點的最短路徑問題。在交通網(wǎng)絡(luò)的路徑分析中，單源最短路徑問題更具有普遍意義，其算法有很多種，其中采用貪心及啟發(fā)策略的Dijkstra算法是目前最完善的，這是荷蘭計

23、算機(jī)科學(xué)教授Edger W.Dijkstra(1930-2002)在1959年發(fā)現(xiàn)的一個算法，它以極強(qiáng)的抗差性得到普及和應(yīng)用。再有就是由弗洛伊德（floyd）提出的另一個算法，又稱傳遞閉包方法，求每一對節(jié)點之間的最短路徑。</p><p>　　本文就從上述幾類來分別介紹最短路徑的幾種常用算法，并介紹最短路徑問題中的算法改進(jìn)。本文的其它部分組織如下：第一章概述了交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)的目的和意義、選題背景

24、和技術(shù)線路。第二章介紹所要用到的技術(shù)原理。第三章介紹最短路徑問題的幾種算法。第四章交通咨詢系統(tǒng)的設(shè)計及實現(xiàn)。第五章為總結(jié)，提出文章的缺點與不足之處，談?wù)勛约旱南敕?，并提出發(fā)展期望。</p><p><b>　　一、緒 論</b></p><p>　　（一）課題的背景和意義</p><p>　　現(xiàn)如今，我國的各大城市都有著交通擁堵、道路堵塞和交通

25、事故的頻繁發(fā)生，這些都隨著城市私家車的不斷增加和城市汽車交通運輸?shù)募涌彀l(fā)展越來越困擾著我們的生活，并且汽車工業(yè)發(fā)展所引發(fā)的道路交通不能滿足實際需求的種種交通問題也越來越嚴(yán)重，越來越突出。為了解決這些問題，除了通常所用的解決辦法，譬如修建必要的道路交通網(wǎng)、針對交通事故多發(fā)路段、修建一系列的交通安全設(shè)施，這些設(shè)施包括道路信號機(jī)、道路標(biāo)識、交通指揮中心等有助于交通安全的設(shè)施，來改善道路的交通環(huán)境，提高交通的順暢性，在一定程度上緩解交通擁擠狀況

26、。而且在必要的時候能夠把道路、車輛、城市的發(fā)展需求等，大都與交通有關(guān)的基本因素歸為一體，在這些基本因素的基礎(chǔ)上，采用信息通信技術(shù)、信息自動采集技術(shù)、電子技術(shù)、網(wǎng)絡(luò)技術(shù)、自動控制以及其他的科學(xué)技術(shù)把它們聯(lián)系起來，開發(fā)一個可供模擬操作的城市交通管理系統(tǒng)。只有將這些方法結(jié)合起來，才能有效地解決隨著交通需求不斷增長、交通系統(tǒng)日益龐大復(fù)雜，所帶來的交通問題。</p><p>　　隨著交通網(wǎng)絡(luò)越來越發(fā)達(dá)，人們在旅游、出差或者

27、其他出行時，不僅會關(guān)心費用問題，而且對里程和所需要的時間等問題也特別感興趣。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問題建立一個交通咨詢系統(tǒng)。這樣的一個交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。</p><p>　　本題目的意義在于，用java軟件技術(shù)實現(xiàn)最短路徑算法在交通咨詢中的重要應(yīng)用，對模擬結(jié)果進(jìn)行分析討論，為將來能夠有效解

28、決各大城市的交通問題提供可靠的依據(jù)。</p><p><b>　?。ǘ┭芯楷F(xiàn)狀</b></p><p>　　本節(jié)闡述三方面問題，首先簡要回顧最短路徑算法研究現(xiàn)狀，然后概要總結(jié)最短路徑算法分類，最后簡單論述最短路徑算法的時間復(fù)雜度。</p><p>　　1.最短路徑算法研究現(xiàn)狀</p><p>　　最短路徑問題一直是計算

29、機(jī)科學(xué)、運籌學(xué)、地理信息科學(xué)等學(xué)科領(lǐng)域的研究熱點。國內(nèi)外大量專家學(xué)者對此問題進(jìn)行了深入研究。</p><p>　　經(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)用范圍等方面各具特色但是因為Dijkstra算法可

30、以給出最可靠的最短路徑，并且容易實現(xiàn)，所以備受青睞和并被廣泛應(yīng)用。</p><p>　　經(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 )

31、優(yōu)先級隊列結(jié)構(gòu)的優(yōu)化；( 5 )基于雙向搜索的并行計算優(yōu)化。</p><p>　　本文所研究的算法內(nèi)容融合了除(4)之外的所有優(yōu)化策略，首先采用堆數(shù)據(jù)結(jié)構(gòu)將Dijkstra算法時間復(fù)雜度降至O(N log N)，然后采用橢圓限制算法搜索區(qū)域，控制搜索規(guī)模，限定搜索方向，最后在本文提出的二樹算法中運用了并行運算思想，極大地降低了最短路徑查詢時間。</p><p>　　2.最短路徑算法分類&l

32、t;/p><p>　　由于問題類型、網(wǎng)絡(luò)特性的不同，最短路徑算法也表現(xiàn)出多樣性。</p><p>　　按照最短路徑問題分類，最短路徑問題通?？煞譃?個基本類型：一是單源最短路徑問題，即查找某一源點到其余各點的最短路徑；另一類是查找某個節(jié)點對之間的最短路徑。</p><p>　　最短路徑問題具體可細(xì)分為以下幾種，單源最短路徑問題，單對節(jié)點間最短路徑、所有節(jié)點間最短路徑、k

33、則最短路徑、實時最短路徑、指定必經(jīng)節(jié)點的最短路徑以及前N條最短路徑問題等，本文的研究范疇屬于單對節(jié)點間最短路徑問題。</p><p>　　按照網(wǎng)絡(luò)類型和表示方法分類，網(wǎng)絡(luò)可以分為稀疏網(wǎng)絡(luò)和非稀疏網(wǎng)絡(luò)，常用的表示方法有鄰接矩陣和鄰接表。</p><p>　　鄰接矩陣方法能夠在o(i)時間內(nèi)查詢到任意兩個節(jié)點之間是否有一條邊，它的空間復(fù)雜度為?，F(xiàn)實生活中網(wǎng)絡(luò)節(jié)點往往很多，動輒上萬，而且是稀疏網(wǎng)

34、絡(luò)居多，比如城市路網(wǎng)，所以用鄰接矩陣表示既不現(xiàn)實，又浪費空間。</p><p>　　鄰接表是另一種存儲網(wǎng)絡(luò)拓?fù)涞臄?shù)據(jù)結(jié)構(gòu)，它是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于交通網(wǎng)絡(luò)等稀疏圖，采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)空間復(fù)雜度僅為O(M十N)，不存在存儲空間的浪費。鄰接表數(shù)據(jù)結(jié)構(gòu)已被證明是網(wǎng)絡(luò)表達(dá)中最有效率的數(shù)據(jù)結(jié)構(gòu)，在最短路徑算法中得到了廣泛應(yīng)用。</p><p><b>　　3.算法時間復(fù)雜

35、度</b></p><p>　　Dijkstra算法最簡單的實現(xiàn)方法是用一個鏈表或者數(shù)組來存儲所有頂點的集合，此時算法的時間復(fù)雜度是 .對于邊數(shù)M遠(yuǎn)少于的稀疏圖來說，為節(jié)省存儲空間，可以用鄰接表更有效的實現(xiàn)該算法;為縮短算法查詢時間，可以將一個二叉堆或者斐波納契堆用作優(yōu)先隊列來尋找最小的頂點。當(dāng)用到二叉堆的時候，算法所需的時間為O((M + N) log N);當(dāng)用斐波納契堆時，算法時間復(fù)雜度為O(M

36、+N1ogN)。對于城市路網(wǎng)，由于N/M介于1.5和2之間所以采用堆數(shù)據(jù)結(jié)構(gòu)，Dijkstra算法時間復(fù)雜度為O(N log N)。</p><p><b>　?。ㄈ┭芯績?nèi)容</b></p><p>　　本文的研究范疇是智能交通系統(tǒng)中的最短路徑算法，研究領(lǐng)域是城市路網(wǎng)中的限制搜索區(qū)域最短路徑算法，研究內(nèi)容是典型城市路網(wǎng)中最短路徑算法的理論研究及實驗驗證，研究目的是保

37、證查詢結(jié)果可靠的情況下，最大程度降低最短路徑查詢時間，研究方法是充分研究和利用城市路網(wǎng)的特征參數(shù)，降低最短路徑算法冗余度和復(fù)雜度，性能驗證是軟件仿真預(yù)測和實測數(shù)據(jù)統(tǒng)計雙重評估標(biāo)準(zhǔn)。</p><p><b>　　（四）論文結(jié)構(gòu)</b></p><p>　　論文共分為六個章節(jié)，各章內(nèi)容組織如下:</p><p>　　第一章為緒論，首先敘述了本課題研

38、究的背景意義，然后依次回顧了智能交通系統(tǒng)的發(fā)展歷程，介紹了最短路徑算法的研究現(xiàn)狀，最終引出論文的工作內(nèi)容并給出了論文組織結(jié)構(gòu)。</p><p>　　第二章是本文的理論研究基礎(chǔ)，介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，著重討論了Dij kstra算法、Floyd算法的運行機(jī)理。</p><p>　　第三章是介紹了系統(tǒng)的開發(fā)工具及系統(tǒng)的運行環(huán)境。</p><p>　

39、　第四章分析交通咨詢系統(tǒng)的最短路徑算法實現(xiàn)代碼的編寫。</p><p>　　第五章簡要介紹了系統(tǒng)的界面設(shè)計。</p><p>　　第六章總結(jié)，提出文章的缺點與不足之處，談?wù)勛约旱南敕?，并提出發(fā)展期望。</p><p>　　二、最短路徑算法相關(guān)原理</p><p>　　本章介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，重點討論Dijkstra算法

40、、Floyd算法的實現(xiàn)原理。</p><p>　?。ㄒ唬〥ijkstra算法 </p><p>　　Dijkstra算法是一個按權(quán)值大小遞增的次序產(chǎn)生最優(yōu)路徑的算法，用于計算從有向圖中任意結(jié)點到其他結(jié)點的最優(yōu)路徑。設(shè)一個有向圖G=(V,E),已知各邊的權(quán)值，以某指定點為源點，求到圖的其余各點的最短路徑。</p><p><b>　　1.算法思想分析<

41、/b></p><p>　　1959年狄克斯特拉（Dijkstra）提出一個按路徑“長度”遞增的次序產(chǎn)生最短路徑的算法，即：把圖中所有的頂點分成兩組，第一組S包括已經(jīng)確定最短路徑的頂點，初始時只含有源點；第二組V-S中包括尚未包括最短路徑的頂點，初始時含有圖中初源點之外的所有其他頂點。按路徑長度遞增的順序計算源點到各頂點的最短路徑，逐個把第二組中的頂點加到第一組中去，直至V=S。</p>&l

42、t;p><b>　　2.實現(xiàn)思路</b></p><p>　　有向網(wǎng)用鄰接矩陣cost[][]表示，其中規(guī)定：（1）如果兩個頂點之間無直接路徑，即弧對應(yīng)權(quán)值為無窮大；（2）兩個頂點之間有直接路徑的，矩陣中的權(quán)值就是弧對應(yīng)的公路長度；（3）對應(yīng)的值為0。S集合初始存放最短路徑的源點，計算過程中將已經(jīng)確定了最短路徑的頂點加到S中去。Dist數(shù)組最終存放源點到各頂點的最短路徑結(jié)果。Path數(shù)

43、組最終存放源點到個頂點的最短路徑經(jīng)過的頂點。</p><p><b>　　3.計算步驟</b></p><p><b>　　如下圖所示：</b></p><p>　　由F到A的路徑有三條：</p><p>　　F A：24；F B A：5+18=23；F B C

44、 A：5+7+9=21</p><p>　　第一條最短路徑為與源點V鄰接頂點的弧集合中，權(quán)值最小的弧。下一條長度次短的最短路徑是：假設(shè)該次短路徑的終點是，則這條路徑或者是，或者是，它的長度或者是從V到弧上的權(quán)值，或者是V到路徑長度與到的弧上權(quán)值之和。</p><p>　　引進(jìn)一個輔助向量D，它的每個分量D[i]表示當(dāng)前找到的從源點V到每個終點的最短路徑的長度。設(shè)用帶權(quán)的鄰接矩陣dist[i

45、][j]來表示有向圖，dist[i][j]表示弧上的權(quán)值，若不存在，則置dist[i][j]為某一最大值。向量S為已找到從V出發(fā)的最短路徑的終點的集合，其初始值為空集。算法按下面的步驟進(jìn)行：</p><p>　?、?從V出發(fā)到圖上其余各個頂點（終點）可能達(dá)到的最短路徑長度的初始值為：</p><p>　　D[i]=dist[ORDINAL(V)][i]，Vi∈V</p>&l

46、t;p>　　其中ORDINAL(V)表示頂點V在有向圖中的序號</p><p><b>　　② 選擇Vj，使</b></p><p>　　D[j]=Min{D[i]|Vi S，Vi∈V}</p><p>　　Vj就是當(dāng)前求得的一條從V出發(fā)的最短路徑的終點，且令</p><p><b>　　S=S∪{j}&

47、lt;/b></p><p>　　即將j加入到S集合中。</p><p>　?、?修改從V出發(fā)到集合V-S上所有頂點Vk可達(dá)到的最短路徑長度。如果</p><p>　　D[j]+dist[j][k]<D[k]</p><p><b>　　則修改D[k]為</b></p><p>　　D

48、[k]=D[j]+dist[j][k]</p><p>　　④ 重復(fù)操作（2），（3）共n-1次。最后求得從V到圖上其余各定點的最短路徑是依路徑長度遞增的序列。</p><p>　　例：對上圖，鄰接矩陣為</p><p>　　最短路徑求解過程圖例，F(xiàn)為源點；</p><p><b>　　初始狀態(tài)，</b></p&g

49、t;<p>　　A B C D E F</p><p><b>　　S </b></p><p><b>　　D </b></p><p>　　求得min{D}={24,5, ∞,25, ∞}=5，最短路徑F B</p><p>

50、;　?、?以D[j]修改（即F B路徑長度修改）向量D，</p><p>　　A B C D E F</p><p><b>　　S </b></p><p><b>　　D </b></p><p>　　求得min{D}={23,12, 2

51、5, ∞}=12，最短路徑F B C</p><p>　?、?以D[j]修改（即F B C路徑長度修改）向量D，</p><p>　　A B C D E F</p><p><b>　　S </b></p><p><b>　　D &l

52、t;/b></p><p>　　求得min{D}={21, 25, ∞}=21，最短路徑F B C A</p><p>　?、?以D[j]修改（即F B C A路徑長度修改）向量D，</p><p>　　A B C D E F</p><p><b>

53、　　S </b></p><p><b>　　D </b></p><p>　　求得min{D}={25, ∞}=25，最短路徑F D</p><p>　　⑤ 以D[j]修改（即F D路徑長度修改）向量D，</p><p>　　A B C D E

54、 F</p><p><b>　　S </b></p><p><b>　　D </b></p><p>　　求得min{D}={∞}=∞，即F E無路徑</p><p>　?。ǘ〧loyd算法</p><p>　　Floyd-Warshall算法（Flo

55、yd-Warshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd-Warshall算法的時間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。</p><p><b>　　1.算法思想原理：</b></p><p>　　Floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來

56、描述的話，首先我們的目標(biāo)是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為這個目標(biāo)重新做一個詮釋（這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在）</p><p>　　從任意節(jié)點i到任意節(jié)點j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個節(jié)點k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點u到節(jié)點v的最短路徑的距離，對于每一個節(jié)點k，我們檢查Dis(i,k) + Dis(k,j) < D

57、is(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。</p><p><b>　　2.算法描述：</b></p><p>　　a.從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，如

58、果兩點之間沒有邊相連，則權(quán)為無窮大。 　　</p><p>　　b.對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。</p><p>　　3.Floyd算法過程矩陣的計算----十字交叉法</p><p>　　方法：兩條線，從左上角開始計算一直到右下角 如下所示給出矩陣，其中矩陣A是鄰接矩陣，而矩陣

59、Path記錄u,v兩點之間最短路徑所必須經(jīng)過的點</p><p><b>　　相應(yīng)計算方法如下：</b></p><p>　　最后A3即為所求結(jié)果。</p><p><b>　　三、開發(fā)工具與環(huán)境</b></p><p><b>　?。ㄒ唬㎎ava技術(shù)</b></p>

60、;<p><b>　　1. Java簡介</b></p><p>　　Java是由SunMicrosystems公司于1995年5月推出的Java程序設(shè)計語言（以下簡稱Java語言）和Java平臺的總稱。用Java實現(xiàn)的HotJava瀏覽器（支持Javaapplet）顯示了Java的魅力：跨平臺、動感的Web、Internet計算。從此，Java被廣泛接受并推動了Web的迅速發(fā)

61、展，常用的瀏覽器現(xiàn)在均支持Javaapplet。另一方面，Java技術(shù)也不斷更新。　　Java平臺由Java虛擬機(jī)（Java Virtual Machine）和Java應(yīng)用編程接口（Application ProgrammingInterface、簡稱API）構(gòu)成。Java應(yīng)用編程接口為Java應(yīng)用提供了一個獨立于操作系統(tǒng)的標(biāo)準(zhǔn)接口，可分為基本部分和擴(kuò)展部分。在硬件或操作系統(tǒng)平臺上安裝一個Java平臺之后，Java應(yīng)用程序就可運行。現(xiàn)

62、在Java平臺已經(jīng)嵌入了幾乎所有的操作系統(tǒng)。這樣Java程序可以只編譯一次，就可以在各種系統(tǒng)中運行。Java應(yīng)用編程接口已經(jīng)從1.1x版發(fā)展到1.2版。目前常用的Java平臺基于Java1.4，最近版本為Java1.6。Java分為三個體系Java</p><p>　　Java的特點是 ：</p><p>　　(1) Java 的簡單性：和C++相比，語法簡單了，取消了指針的語法；內(nèi)存分

63、配和回收不需要我們來過渡關(guān)注，C++可以多繼承，但java只能是單繼承，相對于類來說。（注：接口可以多繼承）使用Asp可以組合HTML頁、腳本命令和ActiveX組件以創(chuàng)建交互的Web頁和基于Web的功能強(qiáng)大的應(yīng)用程序。</p><p>　　(2) java面向?qū)ο螅簀ava算是純面向?qū)ο?，但jquery是更純的面向?qū)ο蟆?在java編程思想這本書說過，“Everything is object!” 這樣便于人類

64、的構(gòu)思和設(shè)計，更符合人們的思考問題方式。</p><p>　　(3) 分布式：主要還是用在EJB上。</p><p>　　(4) 安全性：java的語法限定了源程序的安全性，首先編譯器會進(jìn)行源代碼的第一步檢查。</p><p>　　(5) 跨平臺：java能夠跨越不同的操作系統(tǒng)平臺，平臺無關(guān)性 怎么跨平臺呢？ 主要是在不同的操作系統(tǒng)中，JVM規(guī)范都是一樣的，被JVM

65、加載成各個操作系統(tǒng)所支持的，屏蔽了底層操作系統(tǒng)的差異。</p><p>　　(6) 高性能：開閉原則---對擴(kuò)展開放，對修改關(guān)閉 java是即時編譯的。</p><p><b>　　(7) 多線程。</b></p><p>　　2.Java的處理流程</p><p>　　(1) 首先編輯 .java源程序。</p&

66、gt;<p>　　(2) 編譯成 .class字節(jié)碼文件byte code（一種二進(jìn)制文件）。 </p><p>　　(3) 最后被java虛擬機(jī)（JVM）加載解釋并執(zhí)行。</p><p>　　四、交通咨詢系統(tǒng)的實現(xiàn)</p><p><b>　　（一）系統(tǒng)分析</b></p><p>　　為了保證系統(tǒng)能夠長

67、期、安全、穩(wěn)定、可靠、高效的運行，系統(tǒng)應(yīng)該滿足以下的性能需求：</p><p>　　統(tǒng)一處理的準(zhǔn)確性和及時性：系統(tǒng)處理的準(zhǔn)確性和及時性是系統(tǒng)的必要性能。在系統(tǒng)設(shè)計和開發(fā)過程中，要充分考慮系統(tǒng)當(dāng)前和將來可能承受的工作量，使系統(tǒng)的處理能力和響應(yīng)時間能夠滿足企業(yè)對員工信息處理的需求。</p><p>　　系統(tǒng)的開放性和可擴(kuò)充性：系統(tǒng)在開發(fā)過程中，應(yīng)該充分考慮以后的可擴(kuò)充性。例如數(shù)據(jù)表中用戶選擇字

68、段方式的改變，用戶查詢的需求也會不斷的更新和完善。所有這些，都要求系統(tǒng)提供足夠的手段進(jìn)行功能的調(diào)整和擴(kuò)充。而要實現(xiàn)這一點，應(yīng)通過系統(tǒng)的開放性來完成，既系統(tǒng)應(yīng)是一個開放系統(tǒng)，只要符合一定的規(guī)范，可以簡單的加入和減少系統(tǒng)的模塊，配置系統(tǒng)的硬件。通過軟件的修補(bǔ)、替換完成系統(tǒng)的升級和更新?lián)Q代。</p><p>　　系統(tǒng)的易用性和易維護(hù)性：要實現(xiàn)這一點，就要求系統(tǒng)應(yīng)該盡量使用用戶熟悉的術(shù)語和中文信息的界面；針對用戶可能出現(xiàn)

69、的使用問題，要提供足夠的在線幫助，縮短用戶對系統(tǒng)熟悉的過程。</p><p><b>　　系統(tǒng)的數(shù)據(jù)要求：</b></p><p>　　(1) 數(shù)據(jù)錄入和處理的準(zhǔn)確性和實時性；</p><p>　　(2) 數(shù)據(jù)的一致性與完整性；</p><p>　　(3) 數(shù)據(jù)的共享與獨立性。</p><p>　

70、　1.系統(tǒng)的設(shè)計內(nèi)容：</p><p>　　設(shè)計一個交通咨詢系統(tǒng)，能讓旅客咨詢?nèi)我庖粋€城市到另一個城市之間的最短路徑問題。</p><p>　　該交通咨詢系統(tǒng)設(shè)計共三部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源路徑問題；最后再實現(xiàn)兩個城市之間的最短路徑問題。</p><p><b>　　2.系統(tǒng)的設(shè)計思想</b></p>&l

71、t;p>　　用鄰接矩陣來存儲交通網(wǎng)絡(luò)圖的信息，運用迪杰斯特拉算法實現(xiàn)圖上單源最短路徑問題，然后運用費洛伊德算法實現(xiàn)圖中任意一對頂點間最短路徑問題，這樣就會實現(xiàn)旅客所要咨詢的問題。</p><p><b>　　3.系統(tǒng)設(shè)計流程</b></p><p>　　該交通咨詢系統(tǒng)要完成城市網(wǎng)絡(luò)圖的存儲，并要實現(xiàn)求任意一個城市頂點到其他城市頂點的最短路徑問題，還要實現(xiàn)任意兩個

72、城市頂點間的最短路徑問題。故設(shè)計要分成三部分，一是建立網(wǎng)絡(luò)交通的存儲結(jié)構(gòu)，二是解決單源最短路徑問題；最后時限兩個城市之間的最短路徑問題。</p><p><b>　　（二）系統(tǒng)功能結(jié)構(gòu)</b></p><p><b>　　1. 系統(tǒng)構(gòu)架設(shè)計</b></p><p><b>　　首先總體的步驟是：</b>

73、;</p><p>　　迪克斯特拉算法的具體流程圖如下：</p><p>　　弗洛伊德算法的具體流程圖如下：</p><p><b>　　2.系統(tǒng)詳細(xì)設(shè)計</b></p><p><b>　　程序源代碼如下：</b></p><p><b>　　//Floyd算法&

74、lt;/b></p><p>　　public class ShortPathALG {</p><p>　　private Drawing[] circleList = null;// 用于存放結(jié)點</p><p>　　private Drawing[] lineList = null;// 用于存放線段</p><p>　　priv

75、ate int mGraph[][] = null;// 用于存儲圖的鄰接矩陣</p><p>　　private int mGraphCopy[][] = null;</p><p>　　private String dis = "";// 最短路徑結(jié)果</p><p>　　private String drawLineRed = "

76、";// 要繪制的紅線路徑</p><p>　　private int circleNum = 0;// 結(jié)點的個數(shù)</p><p>　　private int lineNum = 0;// 線段的個數(shù)</p><p>　　private DrawJPanel drawJPanel = null;</p><p>　　public

77、ShortPathALG(DrawJPanel draw) {</p><p>　　drawJPanel = draw;</p><p>　　// TODO 最短路徑的算法 初始化 結(jié)點 和線</p><p>　　circleList = drawJPanel.getCircleList();// 獲得結(jié)點對象數(shù)組</p><p>　　lin

78、eList = drawJPanel.getLineList();// 獲得線段對象數(shù)組</p><p>　　circleNum = drawJPanel.getCircleCount();// 獲得結(jié)點的個數(shù)</p><p>　　lineNum = drawJPanel.getLineCount();</p><p>　　mGraph = new int[circ

79、leNum][circleNum];// 為鄰接矩陣分配空間 0行 、0列 不用</p><p>　　for (int i = 0; i < circleNum; i++) {// 初始化鄰接矩陣 全賦值為 -1 （距離不可能是負(fù)數(shù)）</p><p>　　for (int j = 0; j < circleNum; j++) {</p><p>　　if

80、 (i == j)</p><p>　　mGraph[i][j] = 0;</p><p><b>　　else {</b></p><p>　　mGraph[i][j] = 32767;</p><p><b>　　}</b></p><p><b>　　}<

81、;/b></p><p><b>　　}</b></p><p>　　changeLineColor();// 初始化線條的顏色</p><p>　　mGraphInitialize();// 初始化鄰接矩陣</p><p>　　path_FLOYD(getmGraphCopy());</p><

82、;p><b>　　}</b></p><p>　　// 初始化線條的顏色</p><p>　　private void changeLineColor() {</p><p>　　for (int i = 1; i < lineNum; i++) {</p><p>　　lineList[i].setColo

83、r(Color.blue);</p><p><b>　　}</b></p><p>　　drawJPanel.repaint();</p><p><b>　　}</b></p><p>　　// 初始化鄰接矩陣</p><p>　　public void mGraphIn

84、itialize() {</p><p>　　for (int i = 1; i < lineNum; i++) {// 循環(huán)遍歷線條的起點與終點</p><p>　　int m = 32767;</p><p><b>　　try{</b></p><p>　　m= Integer.parseInt(lineLi

85、st[i].name);//如果輸入的距離不能轉(zhuǎn)換成整形 默認(rèn)距離是1 </p><p>　　}catch(Exception e) {</p><p><b>　　m = 1;</b></p><p><b>　　}</b></p><p><b>　　// 構(gòu)建無向圖</b>

86、;</p><p>　　if (lineList[i].name.equals(""))</p><p><b>　　m = 1;</b></p><p>　　mGraph[lineList[i].xLocation][lineList[i].yLocation] = m;</p><p>　　mGr

87、aph[lineList[i].yLocation][lineList[i].xLocation] = m;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　// 輸出鄰接矩陣</b></p><p>　　public

88、 void showMGraph() {</p><p>　　String s = "最短路徑的鄰接矩陣是(無向圖)：\n";</p><p>　　for (int i = 1; i < circleNum; i++) {</p><p>　　if (!circleList[i].name.equals("")) {&l

89、t;/p><p>　　s = s + circleList[i].name + " ";</p><p><b>　　} else {</b></p><p>　　s = s + i + " ";</p><p><b>　　}</b></p>

90、<p><b>　　}</b></p><p>　　s = s + "\n";</p><p>　　for (int i = 1; i < circleNum; i++) {</p><p>　　for (int j = 1; j < circleNum; j++) {</p><

91、;p>　　s = s + mGraph[i][j] + " ";</p><p><b>　　}</b></p><p>　　s = s + "\n";</p><p><b>　　}</b></p><p><b>　　s = dis;&

92、lt;/b></p><p>　　lineColor();// 修改路徑的顏色</p><p>　　JOptionPane.showMessageDialog(drawJPanel, s, "最短路徑",</p><p>　　JOptionPane.PLAIN_MESSAGE);</p><p><b>　

93、　}</b></p><p>　　// 修改路徑的顏色</p><p>　　private void lineColor() {// 修改路徑的顏色</p><p>　　int gv[];// 存放線段頂點</p><p>　　int i = 1;</p><p>　　StringTokenizer tok

94、enizer = new StringTokenizer(drawLineRed, "-->");</p><p>　　gv = new int[tokenizer.countTokens() + 1];// 動態(tài)的決定數(shù)組的長度</p><p>　　while (tokenizer.hasMoreTokens()) {</p><p>　

95、　String d = tokenizer.nextToken();</p><p>　　gv[i] = Integer.valueOf(d);// 將字符串轉(zhuǎn)換為整型</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　for (int j =

96、 1; j < gv.length - 1; j++) {</p><p>　　for (i = 1; i < lineNum; i++) {</p><p>　　boolean x = lineList[i].xLocation == gv[j]</p><p>　　&& lineList[i].yLocation == gv[j +

97、1];</p><p>　　boolean y = lineList[i].yLocation == gv[j]</p><p>　　&& lineList[i].xLocation == gv[j + 1];</p><p>　　if (x || y) {</p><p>　　lineList[i].setColor(Col

98、or.red);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　drawJPanel.repaint();</p><p><b>　　}</b

99、></p><p>　　// 最短路徑算法FLOYD 算法</p><p>　　int D[][] = null;// D存放每對頂點之間的最短路徑值</p><p>　　int path[][] = null;// p存放每對頂點之間的最短路徑</p><p>　　int length = 0;</p><p>

100、;　　public void path_FLOYD(int data[][]) {</p><p>　　int i, j, k;</p><p>　　length = data.length;</p><p>　　D = new int[length][length];// D存放每對頂點之間的最短路徑值</p><p>　　path = n

101、ew int[length][length];// p存放每對頂點之間的最短路徑</p><p>　　for (i = 1; i < length; i++) {// 各節(jié)點之間的初始已知路徑及距離</p><p>　　for (j = 1; j < length; j++) {</p><p>　　D[i][j] = data[i][j];//<

102、/p><p>　　path[i][j]= -1;</p><p><b>　　}</b></p><p><b>　　}// for </b></p><p>　　for (k = 1; k < length; k++) {</p><p>　　for (i = 1; i

103、< length; i++) {</p><p>　　for (j = 1; j < length; j++) {</p><p>　　if (i == j)// 對角線上的元素（即頂點自身之間）不予考慮</p><p><b>　　continue;</b></p><p>　　if (D[i][k] +

104、D[k][j] < D[i][j]) {// 從i經(jīng)k到j(luò)的一條路徑更短</p><p>　　D[i][j] = D[i][k] + D[k][j];</p><p>　　path[i][j]=k;</p><p><b>　　}</b></p><p><b>　　}</b></p&g

105、t;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public void path_DIJKSTRA(int data[][]) {</p><p>　　int i, j, k;

106、</p><p>　　length = data.length;</p><p>　　D = new int[length][length];// D存放每對頂點之間的最短路徑值</p><p>　　path = new int[length][length];// p存放每對頂點之間的最短路徑</p><p>　　for (i = 1; i

107、 < length; i++) {// 各節(jié)點之間的初始已知路徑及距離</p><p>　　for (int y = 2; y <= data.length; y++) {</p><p>　　if (table[1][y] > 0)// 如果y相鄰于1</p><p>　　L.set(y, length(1, y));</p>&l

108、t;p><b>　　else</b></p><p>　　L.set(y, Integer.MAX_VALUE);</p><p><b>　　}</b></p><p>　　for (int j = 1; j <= V.size() - 1; j++) {</p><p>　　int

109、y = findTheMinInL();</p><p><b>　　X.add(y);</b></p><p>　　Y.remove(y);</p><p>　　for (int jj = 1; jj < table.length; jj++) {</p><p>　　if(table[y][jj]>0)&

110、lt;/p><p>　　if (Y.contains(jj)</p><p>　　&& ((L.get(y) + length(y, jj))< L.get(jj)))</p><p>　　L.set(jj, L.get(y) + length(y, jj));</p><p><b>　　}</b>&

111、lt;/p><p><b>　　}</b></p><p>　　int i, j, k;</p><p>　　length = data.length;</p><p>　　D = new int[length][length];// D存放每對頂點之間的最短路徑值</p><p>　　path =

112、new int[length][length];// p存放每對頂點之間的最短路徑</p><p>　　for (i = 1; i < length; i++) {// 各節(jié)點之間的初始已知路徑及距離</p><p>　　for (j = 1; j < length; j++) {</p><p>　　D[i][j] = data[i][j];//<

113、;/p><p>　　path[i][j]= -1;</p><p><b>　　}</b></p><p><b>　　}// for </b></p><p>　　for (k = 1; k < length; k++) {</p><p>　　for (i = 1; i

114、 < length; i++) {</p><p>　　for (j = 1; j < length; j++) {</p><p>　　if (i == j)// 對角線上的元素（即頂點自身之間）不予考慮</p><p><b>　　continue;</b></p><p>　　if (D[i][k] +

115、 D[k][j] < D[i][j]) {// 從i經(jīng)k到j(luò)的一條路徑更短</p><p>　　D[i][j] = D[i][k] + D[k][j];</p><p>　　path[i][j]=k;</p><p><b>　　}</b></p><p><b>　　}</b></p&

116、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　// 最短路徑輸出</b></p><p>　　public String disPath(in

117、t i, int j) {</p><p>　　// TODO Auto-generated method stub</p><p>　　boolean c1Name = !circleList[i].name.equals("");</p><p>　　boolean c2Name = !circleList[j].name.equals(&q

118、uot;");</p><p>　　if (D[i][j] == 32767) {</p><p>　　if (i != j) {</p><p>　　if (c1Name) {</p><p>　　dis = "從" + circleList[i].name + "到";</p>

119、<p><b>　　} else {</b></p><p>　　dis = "從" + i + "到";</p><p><b>　　}</b></p><p>　　if (c2Name) {</p><p>　　dis += circleLi

120、st[j].name + "沒有路徑\n";</p><p><b>　　} else {</b></p><p>　　dis += j + "沒有路徑\n";</p><p><b>　　}</b></p><p><b>　　}</b>

121、;</p><p><b>　　} else {</b></p><p>　　if (c1Name) {</p><p>　　dis = "從" + circleList[i].name + "到";</p><p><b>　　} else</b></

122、p><p>　　dis = "從" + i + "到";</p><p>　　if (c2Name) {</p><p>　　dis += circleList[j].name + "路徑為: ";</p><p><b>　　} else</b></p>