【正文】 he corresponding reasonable solution. Key words：traffic advisory shortest path Dijkstra algorithm Floyd algorithm1序 言最短路徑問題一直在計(jì)算機(jī)科學(xué)、交通工程學(xué)、地理信息系統(tǒng)、運(yùn)籌學(xué)等學(xué)科中是一個研究的熱點(diǎn)，它不僅是資源分配問題解決的基礎(chǔ)，更是線路選擇問題解決的基礎(chǔ)，特別是在地圖、車輛調(diào)度以及路由選擇方面有著廣泛的應(yīng)用。本文的其它部分組織如下：第一章概述了交通咨詢系統(tǒng)的最短路徑算法與實(shí)現(xiàn)的目的和意義、選題背景和技術(shù)線路。經(jīng)典的圖論與不斷發(fā)展完善的計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。當(dāng)用斐波納契堆時，算法4時間復(fù)雜度為 O(M+N1ogN)。Dist 數(shù)組最終存放源點(diǎn)到各頂點(diǎn)的最短路徑結(jié)果。所以，我們假設(shè) Dis(i,j)為節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的最短路徑的距離，對于每一個節(jié)點(diǎn) k，我們檢查 Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短，我們便設(shè)置 Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn) k，Dis(i,j)中記錄的便是 i 到 j 的最短路徑的距離。目前常用的 Java 平臺基于 ，最近版本為 。系統(tǒng)的開放性和可擴(kuò)充性：系統(tǒng)在開發(fā)過程中，應(yīng)該充分考慮以后的可擴(kuò)充性。private String dis = 。else {mGraph[i][j] = 32767。}}// 輸出鄰接矩陣public void showMGraph() {String s = 最短路徑的鄰接矩陣是(無向圖)：\n。// 存放線段頂點(diǎn)int i = 1。if (x || y) {lineList[i].setColor()。 k length。 y++) { if (table[1][y] 0)// 如果 y 相鄰于 1 (y, length(1, y))。// p 存放每對頂點(diǎn)之間的最短路徑for (i = 1。boolean c2Name = !circleList[j].()。// 存放路徑String lineString = 。return mGraphCopy。}public void changeFlag() {// 修改訪問狀態(tài)。}}}// 該點(diǎn)到頂尖 id 的 距離。(p)。}public static Point getTopointMin(ArrayListPoint arr, Point p) {Point temp = null。調(diào)查表明人們在出行時往往更傾向于轉(zhuǎn)車次數(shù)較少的路線，這樣便降低了人們的辦事效率。圖論[M].北京，北京理工大學(xué)出版社，1997. [5] 陸鋒。參 考 文 獻(xiàn)[1] 嚴(yán)蔚敏。交通咨詢現(xiàn)代化作為城市現(xiàn)代化的重要內(nèi)容，首先應(yīng)是城市居民的生活交通現(xiàn)代化，這是以人為本原則的基本含義和根本要求。Point p1 = getTopointMin(arr, (i))。 i sum。flag = false。BufferedReader bufr = new BufferedReader(new InputStreamReader())。 i 。} else {dis += ppath(i, j) + j + \n 路徑長度為: + D[i][j] + \n。 j++) {if (i == j)// 對角線上的元素（即頂點(diǎn)自身之間）不予考慮continue。 } }int i, j, k。// p 存放每對頂點(diǎn)之間的最短路徑for (i = 1。 j length。 lineList[i].yLocation == gv[j + 1]。}s = dis。//如果輸入的距離不能轉(zhuǎn)換成整形 默認(rèn)距離是 1 }catch(Exception e) {m = 1。 i circleNum。（二）系統(tǒng)功能結(jié)構(gòu)1. 系統(tǒng)構(gòu)架設(shè)計(jì)首先總體的步驟是：迪克斯特拉算法的具體流程圖如下：13弗洛伊德算法的具體流程圖如下：14程序源代碼如下：//Floyd 算法public class ShortPathALG {private Drawing[] circleList = null。(2) 編譯成 .class 字節(jié)碼文件 byte code（一種二進(jìn)制文件） 。在硬件或操作系統(tǒng)平臺上安裝一個 Java 平臺之后，Java 應(yīng)用程序就可運(yùn)行。FloydWarshall 算法的時間復(fù)雜度為 O(N3)，空間復(fù)雜度為 O(N2)。51959 年狄克斯特拉（Dijkstra）提出一個按路徑“長度”遞增的次序產(chǎn)生最短路徑的算法，即：把圖中所有的頂點(diǎn)分成兩組，第一組 S 包括已經(jīng)確定最短路徑的頂點(diǎn)，初始時只含有源點(diǎn)；第二組 VS 中包括尚未包括最短路徑的頂點(diǎn)，初始時含有圖中初源點(diǎn)之外的所有其他頂點(diǎn)。鄰接表數(shù)據(jù)結(jié)構(gòu)已被證明是網(wǎng)絡(luò)表達(dá)中最有效率的數(shù)據(jù)結(jié)構(gòu)，在最短路徑算法中得到了廣泛應(yīng)用。本題目的意義在于，用 java 軟件技術(shù)實(shí)現(xiàn)最短路徑算法在交通咨詢中的重要應(yīng)用，對模擬結(jié)果進(jìn)行分析討論，為將來能夠有效解決各大城市的交通問題提供可靠的依據(jù)。按照起點(diǎn)終點(diǎn)及路徑的數(shù)據(jù)和特征，最短路徑問題可分為五種類型：兩個節(jié)點(diǎn)間的最短路徑、所有節(jié)點(diǎn)的最短路徑、K則最短路徑、實(shí)時最短路徑和指定必經(jīng)點(diǎn)的最短路徑問題。這樣的一個交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準(zhǔn)用徒手畫3）畢業(yè)論文須用 A4 單面打印，論文 50 頁以上的雙面打印4）圖表應(yīng)繪制于無格子的頁面上5）軟件工程類課題應(yīng)有程序清單，并提供電子文檔1）設(shè)計(jì)（論文）2）附件：按照任務(wù)書、開題報告、外文譯文、譯文原文（復(fù)印件）次序裝訂IV目錄序 言 ...........................................................................................................1一、緒 論 ....................................................................................................2（一）課題的背景和意義 ..................................................................................................2（二）研究現(xiàn)狀 ..................................................................................................................2 ....................................................................................................................2 ............................................................................................................................3 ................................................................................................................................3（三）研究內(nèi)容 ..................................................................................................................4（四）論文結(jié)構(gòu) ..................................................................................................................4二、最短路徑算法相關(guān)原理 ........................................................................4（一）DIJKSTRA 算法 .............................................................................................................4 ....................................................................................................................................5 ...........................................................................................................................................5 ...........................................................................................................................................5（二）FLOYD 算法 ................................................................................................................7： ................................................................................................................................8： ........................................................................................................................................8 算法過程矩陣的計(jì)算十字交叉法 .....................................................................................8三、開發(fā)工具與環(huán)境 ..................................................................................10（一）JAVA 技術(shù) ................................................................................................................101. Java 簡介 .............................