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

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

2、<p>　　專 業(yè)： 信息管理與信息系統(tǒng) </p><p>　　班 級(jí)： </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>　　（二）研究現(xiàn)狀2</b></p><p>　　1.最短路徑算法研究現(xiàn)狀2</p>

4、<p>　　2.最短路徑算法分類3</p><p>　　3.算法時(shí)間復(fù)雜度3</p><p><b>　?。ㄈ┭芯?jī)?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.實(shí)現(xiàn)思路5</b></p><p><b>　　3.計(jì)算步驟5</b></p><p>　　（二）Floyd算法7</p><p>　　1.算法思想原理：8&l

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

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

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

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

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

11、<p>　　本文通過對(duì)幾個(gè)常見的最短路徑算法的分析，研究和實(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)化過程中需要特別處理的幾個(gè)問題，并在理論上給出相應(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ì)算機(jī)科學(xué)、交通工程學(xué)、地理信息系統(tǒng)、運(yùn)籌學(xué)等學(xué)科中是一個(gè)研究的熱點(diǎn)，它不僅是資源分配問題解決的基礎(chǔ)，更是線路選擇問題解決的

20、基礎(chǔ)，特別是在地圖、車輛調(diào)度以及路由選擇方面有著廣泛的應(yīng)用。最短路徑問題最直接的應(yīng)用當(dāng)數(shù)在地理信息領(lǐng)域中，例如：GIS網(wǎng)絡(luò)分析、城市規(guī)劃、電子導(dǎo)航等等。在交通咨詢方面，尋找交通網(wǎng)路中兩個(gè)城市之間最短的行車路線就是最短路徑問題的一個(gè)典型的例子。在網(wǎng)絡(luò)通信領(lǐng)域，信息包傳遞的路徑選擇問題也與最短路徑息息相關(guān)。例如OPSF開放路由選擇協(xié)議，每一個(gè)OPSF路由器都維護(hù)一個(gè)描述自治系統(tǒng)范圍內(nèi)到每個(gè)目標(biāo)的最短路徑。在圖像分割問題中，最短路徑也有直接的

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

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

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

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

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

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

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

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

29、機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科領(lǐng)域的研究熱點(diǎn)。國(guó)內(nèi)外大量專家學(xué)者對(duì)此問題進(jìn)行了深入研究。</p><p>　　經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。常用的路徑規(guī)劃方法有:平行最短路徑搜索算法，蟻群算法，基于矩陣負(fù)載平衡的啟發(fā)算法, EBSP*算法和Dijkstra算法等。創(chuàng)門在空間復(fù)雜度、時(shí)間復(fù)雜度、易實(shí)現(xiàn)性及應(yīng)用范圍等方面各具特色但是因?yàn)镈ijkstra算法可

30、以給出最可靠的最短路徑，并且容易實(shí)現(xiàn)，所以備受青睞和并被廣泛應(yīng)用。</p><p>　　經(jīng)典的Dijkstra算法的時(shí)間復(fù)雜度為，直接應(yīng)用到大規(guī)模城市路網(wǎng)時(shí)，最短路徑查詢時(shí)間難以令人接受，專家學(xué)者紛紛開展Dij kstra優(yōu)化算法研究，概括起來，以往研究者主要是從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 )

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

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

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

34、絡(luò)居多，比如城市路網(wǎng)，所以用鄰接矩陣表示既不現(xiàn)實(shí)，又浪費(fèi)空間。</p><p>　　鄰接表是另一種存儲(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)用。</p><p><b>　　3.算法時(shí)間復(fù)雜

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

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

37、證查詢結(jié)果可靠的情況下，最大程度降低最短路徑查詢時(shí)間，研究方法是充分研究和利用城市路網(wǎng)的特征參數(shù)，降低最短路徑算法冗余度和復(fù)雜度，性能驗(yàn)證是軟件仿真預(yù)測(cè)和實(shí)測(cè)數(shù)據(jù)統(tǒng)計(jì)雙重評(píng)估標(biāo)準(zhǔn)。</p><p><b>　　（四）論文結(jié)構(gòu)</b></p><p>　　論文共分為六個(gè)章節(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算法的運(yùn)行機(jī)理。</p><p>　　第三章是介紹了系統(tǒng)的開發(fā)工具及系統(tǒng)的運(yùn)行環(huán)境。</p><p>　

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

40、、Floyd算法的實(shí)現(xiàn)原理。</p><p>　?。ㄒ唬〥ijkstra算法 </p><p>　　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)的最短路徑。</p><p><b>　　1.算法思想分析<

41、/b></p><p>　　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。</p>&l

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

43、組最終存放源點(diǎn)到個(gè)頂點(diǎn)的最短路徑經(jīng)過的頂點(diǎn)。</p><p><b>　　3.計(jì)算步驟</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>　　第一條最短路徑為與源點(diǎn)V鄰接頂點(diǎn)的弧集合中，權(quán)值最小的弧。下一條長(zhǎng)度次短的最短路徑是：假設(shè)該次短路徑的終點(diǎn)是，則這條路徑或者是，或者是，它的長(zhǎng)度或者是從V到弧上的權(quán)值，或者是V到路徑長(zhǎng)度與到的弧上權(quán)值之和。</p><p>　　引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D[i]表示當(dāng)前找到的從源點(diǎn)V到每個(gè)終點(diǎn)的最短路徑的長(zhǎng)度。設(shè)用帶權(quán)的鄰接矩陣dist[i

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

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

47、lt;/b></p><p>　　即將j加入到S集合中。</p><p>　?、?修改從V出發(fā)到集合V-S上所有頂點(diǎn)Vk可達(dá)到的最短路徑長(zhǎng)度。如果</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到圖上其余各定點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。</p><p>　　例：對(duì)上圖，鄰接矩陣為</p><p>　　最短路徑求解過程圖例，F(xiàn)為源點(diǎ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路徑長(zhǎng)度修改）向量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路徑長(zhǎng)度修改）向量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路徑長(zhǎng)度修改）向量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路徑長(zhǎng)度修改）向量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）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。</p><p><b>　　1.算法思想原理：</b></p><p>　　Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語言來

56、描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋（這個(gè)詮釋正是動(dòng)態(tài)規(guī)劃最富創(chuàng)造力的精華所在）</p><p>　　從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個(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) < 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é)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。</p><p><b>　　2.算法描述：</b></p><p>　　a.從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如

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

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

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

61、展，常用的瀏覽器現(xiàn)在均支持Javaapplet。另一方面，Java技術(shù)也不斷更新?！　ava平臺(tái)由Java虛擬機(jī)（Java Virtual Machine）和Java應(yīng)用編程接口（Application ProgrammingInterface、簡(jiǎn)稱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)行。現(xiàn)

62、在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è)體系Java</p><p>　　Java的特點(diǎn)是 ：</p><p>　　(1) Java 的簡(jiǎn)單性：和C++相比，語法簡(jiǎn)單了，取消了指針的語法；內(nèi)存分

63、配和回收不需要我們來過渡關(guān)注，C++可以多繼承，但java只能是單繼承，相對(duì)于類來說。（注：接口可以多繼承）使用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è)計(jì)，更符合人們的思考問題方式。</p><p>　　(3) 分布式：主要還是用在EJB上。</p><p>　　(4) 安全性：java的語法限定了源程序的安全性，首先編譯器會(huì)進(jìn)行源代碼的第一步檢查。</p><p>　　(5) 跨平臺(tái)：java能夠跨越不同的操作系統(tǒng)平臺(tái)，平臺(tái)無關(guān)性 怎么跨平臺(tái)呢？ 主要是在不同的操作系統(tǒng)中，JVM規(guī)范都是一樣的，被JVM

65、加載成各個(gè)操作系統(tǒng)所支持的，屏蔽了底層操作系統(tǒng)的差異。</p><p>　　(6) 高性能：開閉原則---對(duì)擴(kuò)展開放，對(duì)修改關(guān)閉 java是即時(shí)編譯的。</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)的實(shí)現(xiàn)</p><p><b>　　（一）系統(tǒng)分析</b></p><p>　　為了保證系統(tǒng)能夠長(zhǎng)

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

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

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

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

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

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

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

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

75、ate int mGraph[][] = null;// 用于存儲(chǔ)圖的鄰接矩陣</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é)點(diǎn)的個(gè)數(shù)</p><p>　　private int lineNum = 0;// 線段的個(gè)數(shù)</p><p>　　private DrawJPanel drawJPanel = null;</p><p>　　public

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

78、eList = drawJPanel.getLineList();// 獲得線段對(duì)象數(shù)組</p><p>　　circleNum = drawJPanel.getCircleCount();// 獲得結(jié)點(diǎn)的個(gè)數(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)遍歷線條的起點(diǎn)與終點(diǎ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[];// 存放線段頂點(diǎn)</p><p>　　int i = 1;</p><p>　　StringTokenizer tok

94、enizer = new StringTokenizer(drawLineRed, "-->");</p><p>　　gv = new int[tokenizer.countTokens() + 1];// 動(dòng)態(tài)的決定數(shù)組的長(zhǎng)度</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存放每對(duì)頂點(diǎn)之間的最短路徑值</p><p>　　int path[][] = null;// p存放每對(duì)頂點(diǎn)之間的最短路徑</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存放每對(duì)頂點(diǎn)之間的最短路徑值</p><p>　　path = n

101、ew int[length][length];// p存放每對(duì)頂點(diǎn)之間的最短路徑</p><p>　　for (i = 1; i < length; i++) {// 各節(jié)點(diǎn)之間的初始已知路徑及距離</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)// 對(duì)角線上的元素（即頂點(diǎn)自身之間）不予考慮</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存放每對(duì)頂點(diǎn)之間的最短路徑值</p><p>　　path = new int[length][length];// p存放每對(duì)頂點(diǎn)之間的最短路徑</p><p>　　for (i = 1; i

107、 < length; i++) {// 各節(jié)點(diǎn)之間的初始已知路徑及距離</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存放每對(duì)頂點(diǎn)之間的最短路徑值</p><p>　　path =

112、new int[length][length];// p存放每對(duì)頂點(diǎn)之間的最短路徑</p><p>　　for (i = 1; i < length; i++) {// 各節(jié)點(diǎn)之間的初始已知路徑及距離</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)// 對(duì)角線上的元素（即頂點(diǎn)自身之間）不予考慮</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>